我的算法书 - Floyd 全源最短路

一句话算法

Floyd 枚举中转点 k，不断判断 i -> k -> j 是否能让 i -> j 更短。

问题模型

给定一张带权图，要求任意两点之间的最短路。

Floyd 适合点数较小、需要全源最短路的场景。边权可以为负，但不能存在负环。

核心直觉

设 dist[i][j] 表示当前已知的 i 到 j 最短路。

当允许点 k 作为中转点时，i 到 j 的最短路只有两种可能：

不经过 k；
经过 k，也就是 i -> k -> j。

所以转移就是：

cpp

        1

        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

状态定义

更形式化地说：

f[k][i][j]

表示从 i 到 j，只允许使用编号不超过 k 的点作为中转点时的最短路。

转移：

f[k][i][j] = \min(f[k-1][i][j],\ f[k-1][i][k]+f[k-1][k][j])

由于第 k 层只依赖第 k-1 层，实际代码可以用二维数组原地更新。

算法步骤

初始化 dist[i][i] = 0。
对每条边 u -> v，设置 dist[u][v] = min(dist[u][v], w)。
枚举中转点 k = 1..n。
枚举起点 i = 1..n。
枚举终点 j = 1..n。
用 dist[i][k] + dist[k][j] 更新 dist[i][j]。

算法证明

核心不变量：处理完中转点 1..k 后，dist[i][j] 等于只允许使用这些点作为中转点时，i 到 j 的最短路。

当 k=0 时，不允许任何中转点，dist 只包含直接边和 dist[i][i]=0，不变量成立。

处理第 k 个点时，任意最短路要么不经过 k，答案仍是旧的 dist[i][j]；要么经过 k，可以拆成 i -> k 和 k -> j 两段，并且这两段只需要使用 1..k-1 作为中转点。

因此使用：

\min(dist[i][j], dist[i][k]+dist[k][j])

可以得到允许 1..k 作为中转点的最短路。归纳到 k=n，所有点都允许作为中转点，答案正确。

复杂度分析

设点数为 $n$ 。

时间复杂度： $O(n^3)$ 。
空间复杂度： $O(n^2)$ 。

Floyd 代码短，但只适合点数较小的图。

代码实现

输入格式：

n m
u1 v1 w1
...
um vm wm

输出任意两点最短路矩阵；不可达输出 INF。

cpp

        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
40
41
42
43
44
45

        #include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 60);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) {
        dist[i][i] = 0;
    }

    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (dist[i][k] == INF) continue;
            for (int j = 1; j <= n; j++) {
                if (dist[k][j] == INF) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j > 1) cout << ' ';
            if (dist[i][j] == INF) cout << "INF";
            else cout << dist[i][j];
        }
        cout << '\n';
    }

    return 0;
}

测试用例

输入：

输出：

0 3 7 9
INF 0 4 6
INF 1 0 2
INF -1 3 0

应用分类详解

Floyd 的本质是全源最短路。只要点数不大，并且要频繁询问任意两点最短距离，就可以考虑 Floyd。

一、任意两点最短路

典型模式： 多次查询 u 到 v 的最短距离。

识别信号： 出现“任意两点”“多组最短路查询”“点数较小”。

核心建模： 先 $O(n^3)$ 预处理，再 $O(1)$ 回答查询。

二、传递闭包

典型模式： 判断点与点之间是否可达。

识别信号： 出现“关系能否传递”“是否间接到达”。

核心建模： 把 min 改成逻辑或，把加法改成逻辑与，就是 Warshall 可达性算法。

三、最小环与路径中转

典型模式： 需要枚举中转点或分析所有点对关系。

识别信号： 点数较小，关系密集。

核心建模： Floyd 的中转点顺序能系统枚举所有路径结构。

经典例题

1. Floyd 模板题

练习三层循环顺序：k 必须在最外层。

2. 多源多查询最短路

点数小、查询多时，Floyd 通常比每次跑 Dijkstra 更直接。

3. 传递闭包问题

判断任意两点是否存在路径，使用 Floyd 思想处理布尔矩阵。