【1】Dijkstra与SPFA等常见最短路算法的分析与比较——Dijkstra
合集目录：
前言
一、Dijkstra（本文）
二、Bellman-ford与SPFA
三、Dijkstra与SPFA的比较
四、Floyd
五、启发式搜索
Dijkstra
1. 算法介绍
大多数人遇到的最短路都是从Dijkstra开始的，它称得上是最短路中最经典的算法，数据结构、算法分析等课程中都会提到这个算法，可见其重要性。
Dijkstra最短路径算法是由荷兰计算机科学家E.W.Dijkstra于20世纪60年代发明的，学习过操作系统的读者肯定对这个名字不会陌生，正是他提出并解决了“死锁”，也就是“哲学家就餐问题”，这其实也只是他成就的冰山一角，可以说Dijkstra对早期计算机科学的发展做出了很大贡献。
下面先给出问题：给定nnn个点，mmm条有向边的非负权图，请你计算从sss出发，到每个点的最短距离。（洛谷P4779 【模板】单源最短路径）
Dijkstra的主要思想是贪心，从已知最短路的集合SSS中选择点，来更新未知最短路径的点。初始情况下集合SSS中只有一个元素sss，也就是起点，依据我们的假设，之后每求得起点sss到某个点kkk的最短路径，就将kkk这个点加入集合SSS，直至size(S)==nsize(S)==nsize(S)==n。我们以dis[i]dis[i]dis[i]数组来表示起点sss到点iii的最短路径的长度，其初始值分两种情况：若起点sss至点iii有一条有向边，则dis[i]dis[i]dis[i]为该有向边的长度；否则dis[i]dis[i]dis[i]为+∞+\infty+∞（即不能到达）。假设下次最短路径的终点为点jjj，则通往该点的最短路径只有两种情况：(s,j)(s, j)(s,j)或（s,k,j）（s, k, j）（s,k,j），kkk为图中的某个已知最短路径的点，通过kkk点更新最短路的过程即为“松弛”。为了得到最优解，我们需要找到距离起点sss最近的点kkk。
Dijkstra的算法原理就是这样，接下来就是如何通过代码来实现。我们每一次松弛操作都可以更新一个点的最短路径，算法未开始时集合SSS中只有一个元素sss，每进行一次松弛操作，都有一个新元素加入集合SSS，所以我们最多需要进行n−1n-1n−1次松弛操作。另外再添加一个vis[i]vis[i]vis[i]数组来表示点iii在不在集合SSS中，这样就可以写出代码（该代码适合没有算法竞赛基础的读者看，使用邻接矩阵存图）：
#include
#define A 1010using namespace std;
const int inf = 0x3f3f3f;int mp[A][A]; // mp[a][b]表示a到b的有向边的距离为mp[a][b]
int n, m, s, dis[A];
bool vis[A];
void dijkstra(int s) {for (int i = 1; i <= n; i++) dis[i] = inf; //dis[i]表示起点s到点i的距离为dis[i]vis[s] = 1; dis[s] = 0; // 默认起点s已加入集合S，自身到自身距离为0for (int i = 1; i < n; i++) {int k = s, dis_min = inf;for (int j = 1; j <= n; j++) // 寻找没被访问过的且离起点距离最小的点，记为kif (!vis[j] and dis[j] < dis_min)k = j, dis_min = dis[j];vis[k] = 1; // 将k加入集合Sfor (int j = 1; j <= n; j++) // 通过k点来进行松弛操作if (dis[j] > dis[k] + mp[k][j])dis[j] = dis[k] + mp[k][j];}
}int main(int argc, char const *argv[]) {cin >> n >> m >> s;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)mp[i][j] = inf;for (int i = 1; i <= m; i++) {int a, b, c;cin >> a >> b >> c; //a--->bmp[a][b] = c;}dijkstra(s);for (int i = 1; i <= n; i++) cout << dis[i] << " ";
}
使用邻接矩阵存图时，注意有重边的情况，要选择最短的边。
代码真正实现起来与理论会有不少的差异，因为需要考虑实际问题的特殊要求和边界情况，所以很难说有标准的模板，只有个人在理解的基础上对最本质的算法进行加工来解决题目。
通过代码可以看出Dijkstra时间复杂度为Θ(n2)\Theta{(n^2)}Θ(n2)（本文不严格讨论时间复杂度）。
大多数教程会放一些图表来对代码的运行过程进行演示，但我更倾向于自己模拟，可以根据上面题目的例子，再结合代码，画一个矩阵来手动模拟算法流程，这样能更深层次地理解算法内涵。
2. 算法常见优化
对于朴素Dijkstra，循环找最小值的过程可以通过队列来优化，一般用优先队列或者pair；通过链式前向星存图，减少循环遍历松弛点的个数。
优先队列实现（可AC洛谷P4779 【模板】单源最短路径）：
#include
#define A 400010using namespace std;
struct node {int next, to, w;}e[A];
int head[A], num;
void add(int fr, int to, int w) {e[++num].next = head[fr]; e[num].to = to;e[num].w = w; head[fr] = num;
}
struct sta {int id, val;friend bool operator < (const sta a, const sta b) {return a.val > b.val;}
};
int dis[A]; bool vis[A];
void dijkstra_heap(int s) {memset(vis, 0, sizeof vis); memset(dis, 0x3f, sizeof dis);priority_queue q; q.push(sta{s, 0}); dis[s] = 0;while (!q.empty()) {int fr = q.top().id; q.pop();if (vis[fr]) continue; vis[fr] = 1;for (int i = head[fr]; i; i = e[i].next) {int ca = e[i].to;if (dis[ca] > dis[fr] + e[i].w) {dis[ca] = dis[fr] + e[i].w;q.push(sta{ca, dis[ca]});}}}
}int main(int argc, char const *argv[]) {int n, m, s; cin >> n >> m >> s;for (int i = 1; i <= m; i++) {int a, b, c; scanf("%d%d%d", &a, &b, &c);add(a, b, c);}dijkstra_heap(s);for (int i = 1; i <= n; i++) printf("%d ", dis[i]);
}
pair排序实现（仅展示代码主体部分）：
void dijkstra_pair(int s) {memset(vis, 0, sizeof vis); memset(dis, 0x3f, sizeof dis);priority_queue, vector >, greater > > q;q.push(make_pair(0, s)); dis[s] = 0;while (!q.empty()) {int fr = q.top().second; q.pop();if (vis[fr]) continue; vis[fr] = 1;for (int i = head[fr]; i; i = e[i].next) {int ca = e[i].to;if (dis[ca] > dis[fr] + e[i].w) {dis[ca] = dis[fr] + e[i].w;q.push(make_pair(dis[ca], ca));}}}
}
优化之后Dijkstra的时间复杂度可以来到Θ(m⋅logn)\Theta{(m·logn)}Θ(m⋅logn)。
3. 边界处理
有读者可能会发现，朴素实现和队列实现在边界处理上有不同的地方：朴素实现一开始设vis[s]=1vis[s]=1vis[s]=1，而队列实现就没有这个语句。
其实对于朴素实现，无论有没有vis[s]=1vis[s]=1vis[s]=1这句话，都不会影响代码的正确性，这是为什么呢？原因在于k=sk=sk=s这个语句。
每种代码实现方法都有其独特的边界处理，需要读者至少对自己的写法有明确的认知。
4. 记录路径
用一个pre[i]pre[i]pre[i]数组，表示在最短路径中，节点iii的前驱为pre[i]pre[i]pre[i]，这样就可以从终点一直回溯到起点，从而得到最短路径。
在代码中，只需在松弛更新最短距离后顺带更新pre[]pre[]pre[]即可。
for (int j = 1; j <= n; j++) // 通过k点来进行松弛操作if (dis[j] > dis[k] + mp[k][j])dis[j] = dis[k] + mp[k][j], pre[j] = k;
路径输出（反向）：
// 这里的输出路径为逆序，若要求从起点到终点，就用一个数组存起来再输出
while (t != s) cout << t << " ", t = pre[t];
cout << s << endl;
5. 局限性
鉴于Dijkstra的贪心思想，这个算法是没有办法处理带负权的图的。
因为Dijkstra每次都会选择最短的边进行松弛，在正权边的情况下是可以保证最优路线的。但是一旦有负权边，就可能有另一条更短的路线，因为之前相对较长的路线可能会因为这个负权边而变得更优，而此时Dijkstra已经确定了这个点的最优路线，无法再次更新，从而导致出错。