本课时有配套视频讲解，购买后即可观看（永久有效）

Floyd-Warshall求任意两点最短路径

一、课上练习

编程练习

任意点最短路径(Floyd)：L49980

二、知识总结

✨ 核心思想

Floyd-Warshall 算法用于求解全源最短路径问题：求图中任意两点之间的最短距离。它是一种基于动态规划的算法，核心思想是逐步引入"中转点"来优化路径。

状态定义：dp[k][i][j] 表示从 $i$ 到 $j$ ，只允许经过编号 $\leq k$ 的顶点作为中转时的最短距离。

状态转移： $dp[k][i][j] = \min(dp[k-1][i][j], \; dp[k-1][i][k] + dp[k-1][k][j])$

即：要么不经过顶点 $k$ （保持原距离），要么经过顶点 $k$ （拼接 $i \to k$ 和 $k \to j$ ）。

由于第一维可以滚动优化，最终只需一个二维数组。

✨ 算法原理

初始化：
- dist[i][i] = 0（自身到自身距离为 0）。
- 如果存在边 $(i, j, w)$ ，则 dist[i][j] = w。
- 其余 dist[i][j] = ∞。

三重循环（最外层枚举中转点

k

）：

for k = 1 to n:
    for i = 1 to n:
        for j = 1 to n:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

判断负环：如果存在 dist[i][i] < 0 的顶点，说明存在负环。

关键： $k$ 必须在最外层循环。这保证了 DP 的正确性——依次考虑是否经过顶点 1, 2, ..., n 作为中转。

✨ 代码实现

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 505;
5const long long INF = 1e18;
6
7long long dist[MAXN][MAXN]; // 最短距离矩阵
8int n, m;
9
10void floyd() {
11    // 核心：三重循环，k在最外层
12    for (int k = 1; k <= n; k++) {
13        for (int i = 1; i <= n; i++) {
14            for (int j = 1; j <= n; j++) {
15                if (dist[i][k] != INF && dist[k][j] != INF) {
16                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
17                }
18            }
19        }
20    }
21}
22
23int main() {
24    ios::sync_with_stdio(false);
25    cin.tie(nullptr);
26
27    cin >> n >> m;
28
29    // 初始化距离矩阵
30    for (int i = 1; i <= n; i++)
31        for (int j = 1; j <= n; j++)
32            dist[i][j] = (i == j) ? 0 : INF;
33
34    // 读入边
35    for (int i = 0; i < m; i++) {
36        int u, v;
37        long long w;
38        cin >> u >> v >> w;
39        dist[u][v] = min(dist[u][v], w); // 处理重边
40    }
41
42    floyd();
43
44    // 输出任意两点最短距离
45    for (int i = 1; i <= n; i++) {
46        for (int j = 1; j <= n; j++) {
47            if (dist[i][j] == INF)
48                cout << "INF";
49            else
50                cout << dist[i][j];
51            if (j < n) cout << " ";
52        }
53        cout << "\n";
54    }
55
56    return 0;
57}

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 505;
5const long long INF = 1e18;
6
7long long dist[MAXN][MAXN];
8int nxt[MAXN][MAXN]; // nxt[i][j] = 从i到j最短路上i的下一跳
9int n, m;
10
11void floyd() {
12    for (int k = 1; k <= n; k++) {
13        for (int i = 1; i <= n; i++) {
14            for (int j = 1; j <= n; j++) {
15                if (dist[i][k] != INF && dist[k][j] != INF &&
16                    dist[i][k] + dist[k][j] < dist[i][j]) {
17                    dist[i][j] = dist[i][k] + dist[k][j];
18                    nxt[i][j] = nxt[i][k]; // 路径经过k，下一跳与i到k相同
19                }
20            }
21        }
22    }
23}
24
25// 输出从s到t的最短路径
26void printPath(int s, int t) {
27    if (dist[s][t] == INF) {
28        cout << "No path" << endl;
29        return;
30    }
31    cout << s;
32    int cur = s;
33    while (cur != t) {
34        cur = nxt[cur][t];
35        cout << " -> " << cur;
36    }
37    cout << endl;
38}
39
40int main() {
41    ios::sync_with_stdio(false);
42    cin.tie(nullptr);
43
44    cin >> n >> m;
45
46    for (int i = 1; i <= n; i++)
47        for (int j = 1; j <= n; j++) {
48            dist[i][j] = (i == j) ? 0 : INF;
49            nxt[i][j] = -1;
50        }
51
52    for (int i = 0; i < m; i++) {
53        int u, v;
54        long long w;
55        cin >> u >> v >> w;
56        if (w < dist[u][v]) {
57            dist[u][v] = w;
58            nxt[u][v] = v; // 直接到达v
59        }
60    }
61
62    floyd();
63
64    // 查询最短路径
65    int q; cin >> q;
66    while (q--) {
67        int s, t; cin >> s >> t;
68        cout << "Distance: " << dist[s][t] << ", Path: ";
69        printPath(s, t);
70    }
71
72    return 0;
73}

✨ 执行示例

图：4 个顶点，6 条边。

边：1→2(3), 1→3(8), 2→3(2), 2→4(5), 3→4(1), 4→1(2)

初始距离矩阵：

     1    2    3    4
1  [ 0    3    8    ∞ ]
2  [ ∞    0    2    5 ]
3  [ ∞    ∞    0    1 ]
4  [ 2    ∞    ∞    0 ]

k=1（考虑经过顶点1中转）：

dist[4][2] = min(∞, dist[4][1]+dist[1][2]) = min(∞, 2+3) = 5
dist[4][3] = min(∞, dist[4][1]+dist[1][3]) = min(∞, 2+8) = 10

k=2（考虑经过顶点2中转）：

dist[1][3] = min(8, dist[1][2]+dist[2][3]) = min(8, 3+2) = 5
dist[1][4] = min(∞, dist[1][2]+dist[2][4]) = min(∞, 3+5) = 8
dist[4][3] = min(10, dist[4][2]+dist[2][3]) = min(10, 5+2) = 7

k=3（考虑经过顶点3中转）：

dist[1][4] = min(8, dist[1][3]+dist[3][4]) = min(8, 5+1) = 6
dist[2][4] = min(5, dist[2][3]+dist[3][4]) = min(5, 2+1) = 3

k=4（考虑经过顶点4中转）：

dist[2][1] = min(∞, dist[2][4]+dist[4][1]) = min(∞, 3+2) = 5
dist[3][1] = min(∞, dist[3][4]+dist[4][1]) = min(∞, 1+2) = 3

最终距离矩阵：

     1    2    3    4
1  [ 0    3    5    6 ]
2  [ 5    0    2    3 ]
3  [ 3    6    0    1 ]
4  [ 2    5    7    0 ]

✨ 解题步骤详解

判断是否适合 Floyd：
- 需要所有点对的最短路 → Floyd。
- 只需单源最短路 → Dijkstra 或 SPFA 更快。
- $V \leq 500$ → Floyd 可行（ $500^3 = 1.25 \times 10^8$ ）。
初始化：自环为 0，有边填权值（重边取 min），无边为 INF。
三重循环：k 在最外层是正确性的保证，切勿写错顺序。
常见应用：
- 求任意两点最短路径。
- 判断图中是否有负环（dist[i][i] < 0）。
- 求图的传递闭包（可达性）：将 min 改为 OR，+ 改为 AND。
- 求图的最小环。

✨ 常见错误

循环顺序错误： $k$ 必须在最外层！写成 i, j, k 会得到错误结果。
初始化 dist[i][i] 不为 0：自环距离应为 0。
INF 相加溢出：两个 INF 相加会溢出，需要先判断 dist[i][k] != INF && dist[k][j] != INF。
重边处理：多条边取最小权值。
$V$ 过大：Floyd 是 $O(V^3)$ ， $V > 500$ 时通常超时。
无向图忘记双向赋值：dist[u][v] 和 dist[v][u] 都要赋值。

✨ 算法评价

指标	分析
时间复杂度	$O(V^3)$
空间复杂度	$O(V^2)$
适用场景	$V \leq 500$ 的全源最短路
优势	代码极短、能处理负权边、功能多样
劣势	$O(V^3)$ 限制了规模
实现难度	非常简单，5 行核心代码

Floyd-Warshall 以其代码简洁和功能多样（最短路、传递闭包、最小环等）成为竞赛中不可或缺的工具。理解其 DP 本质是关键。