专题：最短路（三）—— Floyd 与全源最短路

本讲定位：图论系列第七讲。前两讲都是单源——给一个起点求到所有点。本讲换个问题：所有点对之间的最短路。它有一个只要三行的算法，而且它的正确性比前两讲都更容易说清，因为它本质上就是一个 DP——弄懂 for k 为什么必须在最外层，等于弄懂了整个算法。本讲做了五组实测：k 写错位置的错误率（写在最内层错 45.0%，写在中间错 50.5%，两种都是”能过样例、挂一半测试点”的典型）；Floyd 的适用区间比想象的窄——实测它的用时几乎与边数无关（$n=500$ 时 $m$ 差 100 倍、用时只差 1.6 倍），所以稠密图上它比 $n$ 遍 Dijkstra 快 1.4～2.0 倍，稀疏图上却慢 2.6～7.7 倍；传递闭包换成 bitset 实测快 101.7 倍（超过理论的 64 倍）；无向图最小环统计答案的位置放错一行错 49.8%；增量 Floyd 在 P1119 的数据规模上比”每次重跑”快 4602 倍。文中所有代码经 g++ -O2 -std=c++14 -Wall 编译运行，P6175、P1119 与洛谷官方样例核对通过。

前置知识：第 01 讲的邻接矩阵（本讲全程用它，这是矩阵存法唯一无可替代的场合）；第 05 讲的松弛操作；第 04 讲”拓扑序即填表顺序”的思想（本讲的 k 就是另一种填表顺序）。建议先看过 dp-series/01——本讲第 2 节的推导是标准 DP 套路，学过 DP 的同学会觉得很亲切。

适合对象：第 2、3 节标 J（Floyd 是 CSP-J 复赛的常客，因为它短到不可能写错——除非 k 放错位置）；第 4～6 节标 S；第 7.2 节（倍增形式）标 S⭐⭐。

1. 一个新问题

前两讲解决的都是”从 $s$ 出发到各点的最短路”。但有些题问的是别的：

• “任意两个城市之间的最短距离是多少？”（$n^2$ 个答案）
• “给定一条必经路线 $a_1 \to a_2 \to \cdots \to a_k$，总代价最少是多少？”（要 $k-1$ 段两两之间的最短路）
• “这张图的直径是多少？”（所有点对最短路的最大值）

朴素办法：跑 $n$ 遍 Dijkstra，每个点当一次源点，复杂度 $O(nm\log m)$。这完全可行，而且在稀疏图上是最优解（第 3 节会给实测）。

但还有一个只要三行的算法，代码短到几乎不可能写错，而且它给出的是一整张 $n\times n$ 的表。更重要的是——它的正确性来自一个非常干净的 DP，弄懂它对理解”什么是阶段”很有帮助。

2. Floyd：三行代码，一个 DP

2.1 先看三行

for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (f[i][k] + f[k][j] < f[i][j])
                f[i][j] = f[i][k] + f[k][j];

初值 f[i][j] = 边 $i\to j$ 的权（无边则 INF，f[i][i] = 0）。跑完之后 f[i][j] 就是 $i$ 到 $j$ 的最短路。复杂度 $O(n^3)$，空间 $O(n^2)$。

很多人到这里就背下来了，然后在考场上把 k 写到里层去。 下面把它推导一遍，你就再也不会记错。

2.2 它其实是一个 DP

关键是给 f 加一个阶段维度：

$$ f[k][i][j] = \text{只允许用编号} \le k \text{的点做中转时，} i \to j \text{的最短路} $$

“中转”指路径中间经过的点，不含两端的 $i$ 和 $j$。