Skip to content

最短路学习笔记

笔记约 2.8 千字
# 图论 # 最短路 # Dijkstra # Floyd # Bellman-Ford # SPFA
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

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

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

#性质

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

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

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

#Dijkstra 算法

该算法的时间复杂度为 O(n2)O(n^2) ，使用堆优化后可达 O(mlog⁡m)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

C++
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(mlog⁡n)O(m \log n)

#实现

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

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

#代码

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

C++
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 次遍历后如果仍能更新最短路径长度则可以判断存在负环。

#代码

C++
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 号点开始走不能保证走到所有的负环，因此需要将节点 1∼n1 \sim n 都入队进行查找。

#卡 SPFA

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

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

#代码

SPFA 求最短路

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

C++
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

C++
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 的节点从 ii 到 jj 的最短路径长度。

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

f∗k,i,j=min⁡(f∗k−1,i,j,f∗k−1,i,k+f∗k−1,k,j)f*{k, i, j} = \min(f*{k - 1, i, j}, f*{k - 1, i, k} + f*{k - 1, k, j})

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

f∗i,j=min⁡(f∗i,j,f∗i,k+f∗k,j)f*{i, j} = \min(f*{i, j}, f*{i, k} + f*{k, j})

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

#代码

C++
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 月。