Acwing Dijkstra

Dijkstra 算法
在此之前，我们先了解一下整体最短路径的一些解决方法。
在这里插入图片描述

单源最短路，指的是求一个点到其它所有点的最短距离（起点是固定的，单一的）
- 所有边权都是正数
- - 朴素Dijkstra，基于贪心；
- - 堆优化Dijkstra。当是稀疏图时，堆优化的效果好一点；当是稠密图时，朴素的好一些
多源汇最短路在最短路问题中，源点也就是起点，汇点也就是终点

最短路问题的核心在于，把问题抽象成一个最短路问题，并建图。图论相关的问题，不侧重于算法的原理，侧重于对问题的抽象（也就是写代码出来才是最牛逼的）

1.朴素Dijkstra

主要思想：用一个集合st来存放最短距离已经确定的点。找到1号点到n号点的最短距离，时间复杂度为 $O(n^2+m)$ ,n表示点数，m表示边数

初始化距离数组dist[]表示1号点到某点的距离dist[1]=0,dist[i]=0x3f3f3f3f为无穷大；
循环n次哦：每次从距离已知的点中，选取一个不在st集合中，且距离起点最短的点t（即在未确定最短路径的节点中，寻找距离最小的节点），然后把t加入到集合st[],表示已经确定有最短路径；
然后遍历一下所有边，用t更新其它点的距离；
当所有点都被遍历完后，判断dist[n]是否还为无穷大，若是则意味着1和n不连通，否则返回dist[n]即为1号点到n号点的最短路距离

先给出板子：

// 返回从1号点到n号点的最短距离
int dijkstra() {memset(dist, 0x3f, sizeof dist);  // 初始化距离数组为无穷大dist[1] = 0;                      // 1号点到自身的距离为0for (int i = 0; i < n; i++) {//进行 n 次循环，以更新 n 个节点的距离int t = -1;//初始化t 为 -1，表示当前最小距离节点尚未找到。// 在未确定最短路径的节点中，寻找距离最小的节点for (int j = 1; j <= n; j++) {if (!st[j] && (t == -1 || dist[j] < dist[t])) {t = j;}}if (t == -1) break;  // 若未找到可更新的节点，跳出循环st[t] = true;  // 将t加入已确定最短路径的集合// 用t点的距离更新其他节点for (int j = 1; j <= n; j++) {//如果通过节点 t 到达节点 j 的距离更小，则更新 dist[j]。dist[j] = min(dist[j], dist[t] + g[t][j]);}}// 如果不存在1-n的最短路，返回-1if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}

Acwing 849.Dijkstra 求最短路 I
在这里插入图片描述

具体实现代码（详解版）：

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 510;int n, m;
int g[N][N];   // 存储每条边
int dist[N];   // 存储1号点到每个点的距离
bool st[N];    // 存储每个点的最短路径是否确定// 返回从1号点到n号点的最短距离
int dijkstra() {memset(dist, 0x3f, sizeof dist);  // 初始化距离数组为无穷大dist[1] = 0;                      // 1号点到自身的距离为0for (int i = 0; i < n; i++) {//进行 n 次循环，以更新 n 个节点的距离int t = -1;//初始化t 为 -1，表示当前最小距离节点尚未找到。// 在未确定最短路径的节点中，寻找距离最小的节点for (int j = 1; j <= n; j++) {if (!st[j] && (t == -1 || dist[j] < dist[t])) {t = j;}}if (t == -1) break;  // 若未找到可更新的节点，跳出循环st[t] = true;  // 将t加入已确定最短路径的集合// 用t点的距离更新其他节点for (int j = 1; j <= n; j++) {//如果通过节点 t 到达节点 j 的距离更小，则更新 dist[j]。dist[j] = min(dist[j], dist[t] + g[t][j]);}}// 如果不存在1-n的最短路，返回-1if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}int main() {cin >> n >> m;// 初始化图，每条边的初始值为无穷大memset(g, 0x3f, sizeof g);while (m--) {int a, b, c;cin >> a >> b >> c;g[a][b] = min(g[a][b], c);  // 更新为最小边权值，防止重边影响}int t = dijkstra();cout << t << endl;return 0;
}

2.堆优化Dijkstra

当图为稀疏图时（点数n和边数m是同一数量级时，如下题），使用堆优化的dijkstra,将时间复杂度由 $O(n^2)$ 降为 $\log n)$ 。堆可以自己手写（用数组模拟），也可以使用现成的（C++的STL提供了优先队列priority_queue，即可使用大根堆和根堆，但相比手写堆不提供任意元素修改）

在这里插入图片描述
实现思路：堆优化，构造小根堆得到当前未加入点中和起点距离最小的点

稀疏图，采用邻接表存储图，单额外增加一个权值数组w[],代表边a和边b的权值；
pair<int,int> PII第一个int表示1号点到该点的距离，第二个int就是该点的编号，利用C++STL优先队列建立小根堆；priority_queue<PII,vector< PII>,greater< PII>> heap;存储当前未加入最短路的点的集合
当堆heap不为空时，取出堆顶元素，即当前未加入中距离起点最近的点，根据该点的出边，更新以该点为中间点后各点与起点的距离是否缩小，若缩小就更新
- 更新距离时，可能对一些距离已知的点进行更新（更新为更小的距离），按理说，应该修改堆中对应节点的距离值，但由于优先队列中的堆不支持直接修改某元素的值，则可以直接插入一个新的节点（此时对于同一个节点，堆中有两份，即冗余存储），但没有关系，在默认情况下，std::pair 的比较首先比较第一个元素，如果第一个元素相等，再比较第二个元素。因此，如果两个 pair 的第一个 int 值相同，将会比较第二个 int 值谁更小，因此更新距离后堆顶依旧是目前未加入点中和起点距离最小的点。**

具体代码实现（详解版）：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;typedef pair<int, int> PII; // 第一个int是到起点距离，第二个int是当前点的编号
const int N = 150010;int h[N], e[N], ne[N], idx, w[N]; // 构建邻接表
int dist[N];// 存储起点到每个节点的最短距离。
int n, m;
bool st[N]; //存储起点到每个节点的最短距离。// 在a和b之间添加一条边，权值为c
void add(int a, int b, int c) {e[idx] = b;ne[idx] = h[a];w[idx] = c; // 存储边的权值h[a] = idx++;
}int dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;// 用优先队列建立小根堆priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1}); // 起点入堆while (heap.size()) {auto t = heap.top(); // 得到堆顶元素，即到起点距离最近的点heap.pop(); // 删除堆顶元素int ver = t.second, distance = t.first; // 得到编号和距离if (st[ver]) continue; // 如果已加入最短路则退出 重新获取堆顶元素st[ver] = true; // 标记加入最短路// 遍历当前节点所连的节点 更新距离for (int i = h[ver]; i != -1; i = ne[i]) {int j = e[i]; // 获得编号dist[j] = min(dist[j],distance + w[i]);heap.push({dist[j],j});//新的距离和节点编号加入优先队列 heap }}return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}int main() {cin >> n >> m;memset(h, -1, sizeof h); // 初始化链表while (m--) {int a, b, c;cin >> a >> b >> c;add(a, b, c);}int t = dijkstra();cout << t << endl;return 0;
}