Skip to content

最短路学习笔记

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由节点和路径组成的)中两节点之间的最短路径。

由于竞赛中不考查文中所述算法的证明,故本文不探讨与证明相关的内容,如有需要请自行查阅维基百科。

#性质

  1. 对于边权为正的图,任意两个节点间的最短路不会重复经过某一个点或某一条边。
  2. 对于边权为正的图,任意两个节点间的最短路中的任意一条的节点数不会超过 nn ,边数不会超过 n1n - 1

#确定起点的最短路径问题

这种问题也叫单源最短路问题,即已知起始节点,求最短路径的问题。在边权非负时适合使用 Dijkstra 算法,若边权为负时则适合使用 Bellman-ford 算法或者 SPFA 算法。

#Dijkstra 算法

该算法的时间复杂度为 O(n2)O(n^2) ,使用堆优化后可达 O(mlogm)O(m \log m)

#演示

Dijkstra 算法每次取出未访问节点中距离最小的节点,并用该节点更新其他节点的距离。(在演示过程中访问过的节点会被标为红色)

#实现

设起点为 11 ,终点为 nn

  1. 初始化 dist1=0dist_1 = 0 ,其余节点的 distdist 值为 \infty
  2. 找出一个未被标记的 distxdist_x 最小的节点 xx ,并将其加入集合 SS
  3. 扫描节点 xx 的所有出边 (u,v,w)(u, v, w) ,若 distv>distu+wdist_v > dist_u + w 则使用 distu+wdist_u + w 更新 distvdist_v
  4. 重复 2、3 两个步骤直到 US=\complement_U S = \emptyset

#代码

题目链接:849. Dijkstra 求最短路 I - AcWing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

int n, m, x, y, z, g[505][505], dist[505];
bool st[505];

int diskstra() {
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
for (int i = 1; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
st[t] = true;
}
return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] = i == j ? 0 : 0x3f3f3f3f;
}
}
for (int i = 1; i <= m; i++) {
cin >> x >> y >> z;
g[x][y] = min(g[x][y], z);
}
cout << diskstra() << endl;
return 0;
}

#堆优化的 Dijkstra 算法

使用堆优化的 Dijkstra 算法的时间复杂度为 O(mlogn)O(m \log n)

#实现

使用堆代替找距离最近的点的操作即可。

由于 C++ STL 中的优先队列不支持删除元素的操作,所以队列中会有重复元素导致复杂度变为 O(mlogm)O(m \log m) ,但比手写堆要容易许多。

#代码

题目链接:850. Dijkstra 求最短路 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;

int n, m, u, v, w, dist[200005];
vector<pair<int, int>> g[200005];
bool st[200005];

void dijkstra() {
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push(make_pair(0, 1));
while (!q.empty()) {
auto t = q.top();
q.pop();
if (st[t.second]) continue;
for (auto i : g[t.second]) {
if (dist[i.first] > t.first + i.second) {
dist[i.first] = t.first + i.second;
q.push(make_pair(dist[i.first], i.first));
}
}
st[tw] = true;
}
}

int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
g[u].push_back(make_pair(v, w));
}
dijkstra();
cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]) << endl;
return 0;
}

#Bellman-Ford 算法

该算法的时间复杂度为 O(nm)O(nm) (对于存在最短路的图)。

#实现

遍历所有边 (u,v,w)(u, v, w) ,若 distv>distu+wdist_v > dist_u + w 则使用 distu+wdist_u + w 更新 distvdist_v ,到没有更新操作发生时停止。

在没有负环的情况下最多遍历 nn 次所有边即可得到最短路。

#判断负环

在第 nn 次遍历后如果仍能更新最短路径长度则可以判断存在负环。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>

using namespace std;

struct node {
int u, v, w;
} g[10005];

int n, m, k, dist[505];

void bellman_ford() {
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= m; j++) {
dist[g[j].v] = min(dist[g[j].v], dist[g[j].u] + g[j].w);
}
}
}

int main() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
cin >> g[i].u >> g[i].v >> g[i].w;
}
bellman_ford();
if (dist[n] > 0x1f1f1f1f) {
cout << "impossible" << endl;
} else {
cout << dist[n] << endl;
}
return 0;
}

#SPFA 算法

SPFA 算法在国际上通称为「队列优化的 Bellman-Ford 算法」,仅在中国大陆地区称为 「SPFA 算法」(Shortest Path Fast Algorithm),在随机图上运行效率为 O(km)O(km)kk 是一个很小的常数),但在特殊构造的图上时间复杂度会退化为为 O(nm)O(nm)

#实现

  1. 先初始化一个队列,并将起点入队。
  2. 取出队头 tt ,并扫描其所有出边 (u,v,w)(u, v, w) ,若 distv>distu+wdist_v > dist_u + w 则使用 distu+wdist_u + w 更新 distvdist_v ,并将 vv 入队。
  3. 重复上述步骤直到队列为空。

#SPFA 判负环

在每次更新 dist[x] 的同时记录当前所走过的边数 cnt[x] = cnt[t] + 1 ,若 cnt[n] 大于等于 nn 则可以证明存在图中负环。

由于从 11 号点开始走不能保证走到所有的负环,因此需要将节点 1n1 \sim n 都入队进行查找。

#卡 SPFA

  1. 生成一棵以起点为根的树,树高尽量高(比如 11 为起点时,可以令每个点 ii 的父亲在 max(i5,1)\max(i - 5, 1)i1i - 1 随机),边权随机,作为最短路径树,同时直接递推求出每个点的带权深度 did_i
  2. 对于剩下的边,端点 (a,b)(a, b) 随机,边权在 dbda|d_b - d_a|dbda+5|d_b - d_a| + 5 随机(如果是有向图则去掉绝对值符号, 55 可以换成其他较小的正数)

这样生成的图中,次短路的条数非常的多,而 SPFA 一旦错误地进入了次短路的分支,就会使得一整棵子树被赋错误的距离,从而在后期不得不重新更新。而由于边权接近,剪枝的效果会受到很大影响。

#代码

SPFA 求最短路

题目:851. spfa 求最短路 - AcWing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>

using namespace std;

int n, m, u, v, w, dist[100005];
vector<pair<int, int>> g[100005];

void spfa() {
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
queue<int> q;
q.push(1);
while (!q.empty()) {
int t = q.front();
q.pop();
for (auto i : g[t]) {
if (dist[i.first] > dist[t] + i.second) {
dist[i.first] = dist[t] + i.second;
q.push(i.first);
}
}
}
}

int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> u >> v >> w;
g[u].push_back(make_pair(v, w));
}
spfa();
if (dist[n] == 0x3f3f3f3f) {
cout << "impossible" << endl;
} else {
cout << dist[n] << endl;
}
return 0;
}

SPFA 判负环

题目:852. spfa 判断负环 - AcWing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;

int n, m, u, v, w, dist[100005], cnt[100005];
vector<pair<int, int>> g[100005];

bool spfa() {
memset(dist, 0x3f, sizeof(dist));
queue<int> q;
for (int i = 1; i <= n; i++) {
q.push(i);
}
while (!q.empty()) {
int t = q.front();
q.pop();
for (auto i : g[t]) {
if (dist[i.first] > dist[t] + i.second) {
dist[i.first] = dist[t] + i.second;
cnt[i.first] = cnt[t] + 1;
if (cnt[i.first] >= n) return true;
q.push(i.first);
}
}
}
return false;
}

int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> u >> v >> w;
g[u].push_back(make_pair(v, w));
}
cout << (spfa() ? "Yes" : "No") << endl;
return 0;
}

#确定终点的最短路径问题

与确定起点的问题相反,该问题是已知终结节点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

只需要反向存图然后再跑一遍单源最短路即可。

#确定起点终点的最短路径问题

即已知起点和终点,求两节点之间的最短路径。

可以使用单源最短路算法并进行剪枝:在处理完到终点的最短路径后直接停止计算最短路。

#全局最短路径问题

全局最短路径问题也叫多源最短路问题,可以求出图中所有的最短路径。适合使用 Floyd 算法,时间复杂度为 O(n3)O(n^3)

#实现

fk,i,jf_{k, i, j} 表示经过若干个编号不超过 kk 的节点从 iijj 的最短路径长度。

容易发现,这个问题可以拆分为两个子问题:经过若干个编号不超过 k1k - 1 的节点从 iijj ,或者从 ii 经过 kk 再到 jj 。可以得出递推式:

fk,i,j=min(fk1,i,j,fk1,i,k+fk1,k,j)f*{k, i, j} = \min(f*{k - 1, i, j}, f*{k - 1, i, k} + f*{k - 1, k, j})

那么接下来考虑优化,在每次循环中只会用到 fk1f_{k - 1} 中的数据,可以使用滚动数组的思想压缩数组,所以递推式可以简化为:

fi,j=min(fi,j,fi,k+fk,j)f*{i, j} = \min(f*{i, j}, f*{i, k} + f*{k, j})

这样即可将空间复杂度优化到 O(n2)O(n^2)

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>

using namespace std;

int n, m, k, x, y, z, f[205][205];

int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = i == j ? 0 : 0x3f3f3f3f3f;
}
}
for (int i = 1; i <= m; i++) {
cin >> x >> y >> z;
f[x][y] = min(f[x][y], z);
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
for (int i = 1; i <= k; i++) {
cin >> x >> y;
if (f[x][y] > 0x1fffffff) {
cout << "impossible" << endl;
} else {
cout << f[x][y] << endl;
}
}
return 0;
}

#参考资料

  1. 最短路 - 图论 - OI Wiki
  2. 最短路问题 - 维基百科
  3. 戴克斯特拉算法 (Dijkstra 算法) - 维基百科
  4. Floyd-Warshall 算法 - 维基百科
  5. Bellman-ford 算法 - 维基百科
  6. 如何看待 SPFA 算法已死这种说法? - immortalCO 的回答 - 知乎
  7. 0x61 最短路,《算法竞赛进阶指南》(ISBN 978-7-83009-313-6,河南电子音像出版社),李煜东,2019 年 9 月。