我的算法书 - 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。

C++

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

C++ 竞赛版

全局数组的精简写法：中转点 k 在最外层，不可达就 continue 防溢出，适合比赛现场手写。

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

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

// Floyd 全源最短路竞赛精简版
// 输入 n m 与 m 条边 u v w，输出任意两点最短路矩阵，不可达输出 INF
// 口诀：中转点 k 必须在最外层；d[i][k] 不可达就 continue，防溢出

const int N = 410;          // 最大点数，按题目改
const long long INF = 1e18; // 大于最长路即可
long long d[N][N];
int n, m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w); // 重边取最小
    }
    for (int k = 1; k <= n; k++) // 中转点最外层，顺序不能换
        for (int i = 1; i <= n; i++) {
            if (d[i][k] == INF) continue;
            for (int j = 1; j <= n; j++)
                if (d[k][j] != INF) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (d[i][j] == INF) cout << "INF";
            else cout << d[i][j];
            cout << " \n"[j == n];
        }
    }
    return 0;
}

Python

C++ 版逻辑在 main 里，Python 版抽成 floyd 函数。

python

        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

        # Floyd-Warshall 全源最短路：dist[i][j] 为 i 到 j 的最短路，INF 表示不可达。
# 点编号 1..n，返回 (n+1)x(n+1) 矩阵（dist[i][i] = 0，下标 0 不用）；边以 (u, v, w) 传入。
# C++ 的 long long 与 INF = 1LL << 60 在 Python 里是任意精度 int，不会溢出。
# 平行边只保留最小权值；不处理负环（有负环时结果无意义）。

INF = 1 << 60  # 哨兵，约 1.15e18，比任何合法路径都大

type Grid = list[list[int]]


def floyd(n: int, edges: list[tuple[int, int, int]]) -> Grid:
    """返回 n+1 阶距离矩阵；dist[0][*] 与 dist[*][0] 恒为 INF，不使用。"""
    dist: Grid = [[INF] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dist[i][i] = 0  # 自己到自己距离 0

    for u, v, w in edges:
        if w < dist[u][v]:  # 平行边保留最小权值，对应 C++ 的 min(dist[u][v], w)
            dist[u][v] = w

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            if dist[i][k] == INF:
                continue  # i 到中转点 k 不可达，松弛无意义
            for j in range(1, n + 1):
                if dist[k][j] == INF:
                    continue
                nd = dist[i][k] + dist[k][j]
                if nd < dist[i][j]:
                    dist[i][j] = nd
    return dist

测试用例

输入：

输出：

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 思想处理布尔矩阵。