做网站师傅360指数

合集目录：

前言

一、Dijkstra（本文）

二、Bellman-ford与SPFA

三、Dijkstra与SPFA的比较

四、Floyd

五、启发式搜索

Dijkstra

1. 算法介绍

大多数人遇到的最短路都是从Dijkstra开始的，它称得上是最短路中最经典的算法，数据结构、算法分析等课程中都会提到这个算法，可见其重要性。
Dijkstra最短路径算法是由荷兰计算机科学家E.W.Dijkstra于20世纪60年代发明的，学习过操作系统的读者肯定对这个名字不会陌生，正是他提出并解决了“死锁”，也就是“哲学家就餐问题”，这其实也只是他成就的冰山一角，可以说Dijkstra对早期计算机科学的发展做出了很大贡献。

下面先给出问题：给定$n$个点，$m$条有向边的非负权图，请你计算从$s$出发，到每个点的最短距离。（洛谷P4779 【模板】单源最短路径）

Dijkstra的主要思想是贪心，从已知最短路的集合$S$中选择点，来更新未知最短路径的点。初始情况下集合$S$中只有一个元素$s$，也就是起点，依据我们的假设，之后每求得起点$s$到某个点$k$的最短路径，就将$k$这个点加入集合$S$，直至$size(S)==n$。我们以$dis[i]$数组来表示起点$s$到点$i$的最短路径的长度，其初始值分两种情况：若起点$s$至点$i$有一条有向边，则$dis[i]$为该有向边的长度；否则$dis[i]$为$+\infty$（即不能到达）。假设下次最短路径的终点为点$j$，则通往该点的最短路径只有两种情况：$(s,j)$或$（s,k,j）$，$k$为图中的某个已知最短路径的点，通过$k$点更新最短路的过程即为“松弛”。为了得到最优解，我们需要找到距离起点$s$最近的点$k$。

Dijkstra的算法原理就是这样，接下来就是如何通过代码来实现。我们每一次松弛操作都可以更新一个点的最短路径，算法未开始时集合$S$中只有一个元素$s$，每进行一次松弛操作，都有一个新元素加入集合$S$，所以我们最多需要进行$n-1$次松弛操作。另外再添加一个$vis[i]$数组来表示点$i$在不在集合$S$中，这样就可以写出代码（该代码适合没有算法竞赛基础的读者看，使用邻接矩阵存图）：

#include <bits/stdc++.h>
#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时间复杂度为$\Theta (n^2)$（本文不严格讨论时间复杂度）。
大多数教程会放一些图表来对代码的运行过程进行演示，但我更倾向于自己模拟，可以根据上面题目的例子，再结合代码，画一个矩阵来手动模拟算法流程，这样能更深层次地理解算法内涵。

2. 算法常见优化

对于朴素Dijkstra，循环找最小值的过程可以通过优先队列来优化，一般用结构体或者pair；并且通过链式前向星存图，减少循环遍历松弛点的个数。
结构体实现（可AC洛谷P4779 【模板】单源最短路径）：

#include <bits/stdc++.h>
#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<sta> 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<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > 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的时间复杂度可以来到$\Theta (m\cdot logn)$。

3. 边界处理

有读者可能会发现，朴素实现和队列实现在边界处理上有不同的地方：朴素实现一开始设$vis[s]=1$，而队列实现就没有这个语句。
其实对于朴素实现，无论有没有$vis[s]=1$这句话，都不会影响代码的正确性，这是为什么呢？原因在于$k=s$这个语句。
每种代码实现方法都有其独特的边界处理，需要读者至少对自己的写法有明确的认知。

4. 记录路径

用一个$pre[i]$数组，表示在最短路径中，节点$i$的前驱为$pre[i]$，这样就可以从终点一直回溯到起点，从而得到最短路径。
在代码中，只需在松弛更新最短距离后顺带更新$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已经确定了这个点的最优路线，无法再次更新，从而导致出错。