最短路学习笔记 - Baoshuo's OI Blog

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

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

#性质

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

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

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

#Dijkstra 算法

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

#演示

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

#实现

设起点为 $1$ ，终点为 $n$ 。

初始化 $dist_1 = 0$ ，其余节点的 $dist$ 值为 $\infty$ 。
找出一个未被标记的 $dist_x$ 最小的节点 $x$ ，并将其加入集合 $S$ 。
扫描节点 $x$ 的所有出边 $(u, v, w)$ ，若 $dist_v > dist_u + w$ 则使用 $dist_u + w$ 更新 $dist_v$ 。
重复 2、3 两个步骤直到 $\complement_U S = \emptyset$ 。

#代码

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

C++

#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(m \log n)$

#实现

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

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

#代码

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

C++

#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)$ （对于存在最短路的图）。

#实现

遍历所有边 $(u, v, w)$ ，若 $dist_v > dist_u + w$ 则使用 $dist_u + w$ 更新 $dist_v$ ，到没有更新操作发生时停止。

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

#判断负环

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

#代码

C++

#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)$ （ $k$ 是一个很小的常数），但在特殊构造的图上时间复杂度会退化为为 $O(nm)$ 。

#实现

先初始化一个队列，并将起点入队。
取出队头 $t$ ，并扫描其所有出边 $(u, v, w)$ ，若 $dist_v > dist_u + w$ 则使用 $dist_u + w$ 更新 $dist_v$ ，并将 $v$ 入队。
重复上述步骤直到队列为空。

#SPFA 判负环

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

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

#卡 SPFA

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

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

#代码

SPFA 求最短路

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

C++

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

#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(n^3)$ 。

#实现

设 $f_{k, i, j}$ 表示经过若干个编号不超过 $k$ 的节点从 $i$ 到 $j$ 的最短路径长度。

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

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

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

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

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

#代码

C++

#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;
}

#参考资料

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