Floyd 全源最短路

1 从单源最短路到全源最短路

在 bellman-ford、dijkstra 中，我们固定起点 $s$，求它到其余各点的最短距离。这叫单源最短路。

如果要回答许多次询问，每次起点、终点都可能不同，就可以预先求出任意两点之间的最短距离，存进矩阵 $d$：$d[i][j]$ 表示从 $i$ 到 $j$ 的最短距离。这叫全源最短路，也叫多源最短路。

逐个选择起点，运行单源最短路算法，也能解决这个问题。Floyd（Floyd–Warshall）则提供了一种只用三重循环的做法，时间复杂度为 $O(n^3)$，适合点数较少、需要大量点对距离的场景。本文先用三维数组完整保存各阶段，再推导如何把空间从 $O(n^3)$ 压缩到 $O(n^2)$。

本文先讨论没有负环的有向图。边权可以为负数；无向图只需把每条边按两个方向存入。

2 从一次绕路想到分阶段求解

从 $i$ 到 $j$，直接走一定最好吗？

不一定。例如直达要花 $8$，先到 $k$ 花 $2$，再从 $k$ 到 $j$ 花 $1$，绕一下反而只需要 $3$。只要两段都可达，就可以尝试更新：

这里的 $i\to k$、$k\to j$ 都可以是一整段路径，不一定是直接相连的一条边。

把所有 $i,j,k$ 枚举一遍，就一定能得到答案吗？

还不能这样下结论。更新 $d[i][j]$ 时，依赖的 $d[i][k]$、$d[k][j]$ 可能还没算好。我们需要安排一种顺序，保证用到的子问题已经解决。

可以先解决一个受限制的问题：不允许经过任何中间点时，只能直接走边，或者留在原地。然后允许经过点 $1$，再允许经过点 $2$，直到所有点都能作为中间点。

新允许一个点作为中间点，会多出哪些走法？

假设之前只允许用 $1,\ldots,k-1$ 作为中间点，现在再允许用 $k$。新增的候选路径一定经过 $k$，于是可以在 $k$ 处拆成 $i\to k$ 和 $k\to j$ 两段。这就找到了分阶段求解的依据。

把上面的两步思考放在一起看：图 (a) 比较一次绕路的费用，图 (b) 说明新开放 $k$ 时，两段距离应当来自已经完成的阶段。

图 (b) 中的省略号表示每段都可以是一整条路径。我们复用的是两段已经求好的距离，再与不经过 $k$ 的旧答案取最小值；并不是要求整条路径只走两条边。

3 动态规划的状态与转移

3.1 状态：限制中间点的编号

定义 $D_k(i,j)$ 表示：从 $i$ 到 $j$，所有中间点都属于集合 $\{1,2,\ldots,k\}$ 时的最短距离；不可达时记为 $\infty$。

中间点指起点与终点之间的点，起点 $i$ 和终点 $j$ 不受这个集合限制。例如计算 $D_2(4,5)$ 时，可以从 $4$ 出发、到 $5$ 结束，只是途中不能经过点 $3$。

3.2 初始状态：没有中间点

$D_0(i,j)$ 只考虑直接走边与留在原地：

• $i=j$ 时为 $0$，表示一条边也不走。
• $i\ne j$ 且有边 $i\to j$ 时，为这些重边中的最小权值。
• 其余情况为 $\infty$。

实现时先把对角线设为 $0$，其余设为 INF，然后读边并取最小值。这样也能保留负权自环；不过负权自环本身就是负环，不符合本文主模板的前提。

3.3 转移：是否经过新开放的点

因为没有负环，路径中的环可以删去而不增加长度，所以对可达点对，总能选出一条简单最短路。按它是否把 $k$ 作为中间点分类：

1. 不经过 $k$：所有中间点仍在 $1,\ldots,k-1$ 内，最优值为 $D_{k-1}(i,j)$。
2. 经过 $k$：简单路径只经过 $k$ 一次，在这里切开后，两段的中间点都在 $1,\ldots,k-1$ 内，分别对应 $D_{k-1}(i,k)$ 与 $D_{k-1}(k,j)$。

因此：

这个式子没有遗漏最优路径：它必然属于上面两类之一。反过来，两段可达路径拼接后也是一条合法走法；即使拼接产生重复点，也可以删去非负的环，使长度不增加。因此两段最短距离的和可以作为候选值。

起点或终点恰好是 $k$ 时，转移依然成立，因为 $D_{k-1}(k,k)=0$，相当于拼上一段长度为零的路径。

初始状态正确，每次转移又完整考虑了新增的走法，于是由归纳可知：处理完第 $k$ 个阶段，得到的正是 $D_k$。当 $k=n$ 时，所有点都允许作为中间点，$D_n$ 就是答案。

4 先把转移直接写成三维代码

4.1 三维数组与转移一一对应

先完整保留阶段这一维。用 d[k][i][j] 存储 $D_k(i,j)$，三个下标依次表示“开放到哪个中间点、起点、终点”。

第 $0$ 层按前面的方法初始化。之后，直接照着转移公式写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // 不经过新开放的 k：继承上一层。
            d[k][i][j] = d[k - 1][i][j];

            // 经过 k：两段距离都从上一层读取。
            if (d[k - 1][i][k] != INF && d[k - 1][k][j] != INF) {
                d[k][i][j] = min(d[k][i][j],
                                d[k - 1][i][k] + d[k - 1][k][j]);
            }
        }
    }
}

这里读的是第 $k-1$ 层，写的是第 $k$ 层，两个阶段保存在不同位置。即使本轮没有找到更短的路径，也必须先继承旧答案，不能把当前状态留成默认的零。

按照这个转移计算时，先算完第 $k-1$ 层，才能算第 $k$ 层，所以把 $k$ 放在最外层；同一层的所有 $(i,j)$ 都只依赖上一层，因此内层 $i,j$ 可以交换。

完整保存第 $0$ 到第 $n$ 层，需要 $(n+1)$ 张距离矩阵，空间复杂度为 $O(n^3)$。每层计算 $n^2$ 个状态，共 $n$ 次转移，时间复杂度为 $O(n^3)$。

4.2 可以直接运行的三维版本

下面是包含初始化、读边、转移和输出的完整程序。它先打印 D[0]，之后每完成一整轮 $k$ 就打印 D[k]，让我们看清每一层的结果。最终答案在 d[n][i][j] 中。

教学版的数组按 $n\le50$ 的小图准备，输入有向图，要求没有负环，距离范围与后面的二维模板采用同样约定。先用小图观察状态，再考虑处理更大的数据。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

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

// 三维教学版：用于 n <= 50 的有向图，要求无负环。
// d[k][i][j]：只允许 1..k 作为中间点时，i 到 j 的最短距离。
// 输出第 0 层及每次转移后的完整矩阵，方便逐层核对。
const int N = 55;
const long long INF = 1000000000000000000LL;
long long d[N][N][N];
int n, m;

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

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[0][i][j] = (i == j ? 0 : INF);

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

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 不经过新开放的 k：继承上一层。
                d[k][i][j] = d[k - 1][i][j];

                // 经过 k：两段距离都从上一层读取。
                if (d[k - 1][i][k] != INF && d[k - 1][k][j] != INF) {
                    d[k][i][j] = min(d[k][i][j],
                                    d[k - 1][i][k] + d[k - 1][k][j]);
                }
            }
        }
        print_layer(k);
    }
    return 0;
}

5 运行三维版本，观察每一层

取 $5$ 个点，点 $5$ 孤立，其余有向边如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 样例图：点 5 孤立，其余为六条边；边旁数字为权值
digraph G {
    rankdir=LR;
    nodesep=0.6;
    ranksep=0.9;
    node [shape=circle, fixedsize=true, width=0.55, fontname="Noto Serif SC", fontsize=15];
    edge [fontname="Noto Serif SC", fontsize=13];
    1 -> 2 [label="8"];
    1 -> 3 [label="2"];
    1 -> 4 [label="20"];
    3 -> 2 [label="1"];
    2 -> 4 [label="2"];
    3 -> 4 [label="7"];
    5 [style=dashed];
}

5.1 输入、编译与完整输出

把上面的程序保存为 floyd_3d.cpp，把下面的输入保存为 sample.in：

1
2
3
4
5
6
7

5 6
1 2 8
1 3 2
1 4 20
3 2 1
2 4 2
3 4 7

在这两个文件所在目录运行：

1
2

g++ -std=c++17 -O2 floyd_3d.cpp -o floyd_3d
./floyd_3d < sample.in

矩阵的行是起点，列是终点。程序的完整输出如下，D[k] 表示只允许 $1,\ldots,k$ 作为中间点时的距离矩阵：

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

D[0]
0 8 2 20 INF
INF 0 INF 2 INF
INF 1 0 7 INF
INF INF INF 0 INF
INF INF INF INF 0

D[1]
0 8 2 20 INF
INF 0 INF 2 INF
INF 1 0 7 INF
INF INF INF 0 INF
INF INF INF INF 0

D[2]
0 8 2 10 INF
INF 0 INF 2 INF
INF 1 0 3 INF
INF INF INF 0 INF
INF INF INF INF 0

D[3]
0 3 2 5 INF
INF 0 INF 2 INF
INF 1 0 3 INF
INF INF INF 0 INF
INF INF INF INF 0

D[4]
0 3 2 5 INF
INF 0 INF 2 INF
INF 1 0 3 INF
INF INF INF 0 INF
INF INF INF INF 0

D[5]
0 3 2 5 INF
INF 0 INF 2 INF
INF 1 0 3 INF
INF INF INF 0 INF
INF INF INF INF 0

可以先在纸上写出第 $0$ 层，再逐层计算，最后与程序输出核对。D[1] 没有变化，D[2] 和 D[3] 有变化，后面几层又保持不变；没有变化的层同样是合法的阶段结果。

5.2 手动核对关键更新

下面只追踪会变化的三个位置，其余位置始终不变。表中的每一行来自相应的第 $k$ 层：

先核对 $k=2$：新允许经过点 $2$ 后，d[2][1][4] 读取的三个数都来自第 $1$ 层：

同一轮还得到 $D_2(3,4)=\min(7,1+2)=3$。接着计算 $k=3$，更新 d[3][1][4] 时，使用第 $2$ 层已经算好的结果：

其中 $D_2(3,4)=3$ 对应整段路径 $3\to2\to4$。所以新开放中转点 $3$ 时，就能拼出 $1\to3\to2\to4$，并不要求路径上的编号递增。

可以先遮住输出，手动完成下面两次检查：

1. 求 d[3][1][2]：应从哪一层取数，为什么会从 $8$ 变成 $3$？
2. 把输入中 $3\to2$ 的边权从 $1$ 改成 $4$，重新手推 d[3][1][4]，再运行程序检查它是否变成 $8$。

点 $5$ 到自身的距离始终为 $0$，它与其他点之间始终不可达。观察这个孤立点，可以检查 INF 是否被正确保留。

下面的动画也可以配合手推使用。先关注三维分层状态，观察每次更新从上一层取了哪两段距离；二维原地更新的理由放在下一节推导。

6 从三维状态推导空间压缩

6.1 更早的层还有用吗？

观察三维转移：计算第 $k$ 层时，只读取第 $k-1$ 层，从不读取第 $k-2$ 层及更早的层。

因此，如果只需要最终最短距离，就不必保留全部历史。先做一步容易确认正确的压缩：用 prev 保存上一层，用 cur 保存当前层，算完一层后交换它们。

假设已经把初始矩阵 $D_0$ 写进 int g[2][maxn][maxn] 的第 $0$ 层（即 g[0]），转移核心可以写成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const int maxn = 410;       // 点数上限，按题目数据范围调整
const int INF = 0x3f3f3f3f; // 两个 INF 相加仍在 int 范围内

int g[2][maxn][maxn];       // g[0] 存 D_0，两层轮流使用

int prev = 0, cur = 1;      // 这两个是“层号”，不是矩阵
for (int k = 1; k <= n; k++) {
    memcpy(g[cur], g[prev], sizeof(g[cur])); // 当前层先完整继承上一层
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[prev][i][k] != INF && g[prev][k][j] != INF) {
                g[cur][i][j] = min(g[cur][i][j], g[prev][i][k] + g[prev][k][j]);
            }
        }
    }
    swap(prev, cur);        // 本轮结果成为下一轮的“上一层”
}
// 循环结束，最终答案在 g[prev]

这时仍然严格区分读、写两个阶段，只是把 $n+1$ 张矩阵缩减成两张，空间降为 $O(n^2)$（准确说是 $2\cdot\text{maxn}^2$）。

换成分层数组之后有三处值得留意：

• prev / cur 从矩阵变成了层号。 它们只是 g 第一维的下标，swap(prev, cur) 交换两个 int，$O(1)$；真正 $O(n^2)$ 的搬动是那句 memcpy。读的时候写 g[prev][i][j]，写的时候写 g[cur][i][j]，读写分离靠名字表达，不再靠两张独立的变量。

• memcpy 抄的是整块 maxn × maxn。 当 $n$ 明显小于 maxn 时，按行只抄 $1\sim n$ 列更划算：

  1
  2
  3

  for (int i = 1; i <= n; i++) {
      memcpy(g[cur][i], g[prev][i], sizeof(int) * (n + 1));
  }
  

  复制

• 为什么可以放心用 int。 INF = 0x3f3f3f3f 两倍仍小于 INT_MAX，而转移里已经先用 != INF 挡住了“不可达 + 任何数”的情形，所以不会溢出。代价是真实的最短距离必须小于 INF：如果边权可能到 $10^9$、路径又要拼很多段，就换回 long long 版本，并把 INF 改成 1e18。

三维教学版为了观察过程而输出每一层；如果题目本身要求保留历史状态，就要按需求保存。下面讨论只需要最终矩阵的情形。

6.2 能不能连两张矩阵也合成一张？

如果直接在一张矩阵里修改，开始第 $k$ 轮时，它保存 $D_{k-1}$；结束这一轮后，它应该变成 $D_k$。真正要检查的是：先更新的位置，会不会覆盖后续转移仍要读取的旧值？

固定 $k$，更新 $(i,j)$ 时，需要的三项是：

• d[i][j]：这个位置在本轮尚未更新，仍是上一层的旧答案。
• d[i][k]：第 $k$ 列的值。
• d[k][j]：第 $k$ 行的值。

每个 $(i,j)$ 在本轮只更新一次，所以第一项没有问题。接下来只需检查第 $k$ 行、第 $k$ 列会不会改变。

无负环时，留在原地的最短距离为 $0$，即 $D_{k-1}(k,k)=0$。因此：

不可达的位置也保持不可达。于是，第 $k$ 行、第 $k$ 列在这一轮中都不会变化：即使它们已经执行过更新，读到的数仍等于上一层的数。其他位置虽然可能变小，却不会被当前阶段用作拼接路径的两段距离。

这就证明了单张矩阵原地更新的安全性。不是看到转移只依赖上一层，就能直接删掉一个下标；还需要确认覆盖旧值不会破坏后续读取。

6.3 最后才得到二维核心

有了上面的证明，才可以把三维代码中的 d[k][i][j] 和 d[k-1][i][j] 合并成同一个 d[i][j]：

1
2
3
4
5
6
7
8
9

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

第 $k$ 轮开始前，矩阵表示 $D_{k-1}$；结束后，矩阵表示 $D_k$。省去的只是保存历史阶段的位置，阶段的推进顺序仍然存在。

两层滚动与原地更新的渐进空间复杂度相同；后者进一步减少了矩阵数量，也省去了每轮复制整张矩阵的操作。它们的核心计算时间仍然都是 $O(n^3)$。

7 压缩后，为什么 k 仍必须在最外层？

按阶段推进，才能保证开始第 $k$ 轮时，所有点对都已完成第 $k-1$ 阶段。内层 $i,j$ 可以交换，$k$ 这一阶段循环则应放在它们外面。

7.1 把 k 放在内层的反例

考虑只有三条边的有向图，边权都为 $1$：

1
2
3
4
5
6
7
8

digraph G {
    rankdir=LR;
    node [shape=circle, width=0.5, fontsize=13];
    edge [arrowsize=0.7, fontsize=11];
    1 -> 3 [label="1"];
    3 -> 4 [label="1"];
    4 -> 2 [label="1"];
}

正确的 $d[1][2]$ 应为 $3$（路径 $1\to3\to4\to2$）。如果按 i → j → k 的顺序、每个循环都从 $1$ 枚举到 $n$，处理 $(i,j)=(1,2)$ 时：

• 枚举到 $k=3$，$d[3][2]$ 还是 INF，无法更新。
• 枚举到 $k=4$，$d[1][4]$ 还是 INF（$1\to4$ 要经过 $3$，而 $3$ 还没被算过），也无法更新。

稍后处理 $(1,4)$ 才得到 $d[1][4]=2$，但算法不会回头重算 $(1,2)$，最终漏掉这条路径。

所以“每个三元组都算过一次”并不足够，依赖的距离必须在使用之前准备好。

8 二维压缩版完整模板

现在再来看竞赛中常用的二维实现。输入与三维版本相同，输出时只保留最终矩阵，不再打印各层。本模板同样要求图中没有负环。

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
46
47
48
49

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

// Floyd 全源最短路竞赛精简版：有向图，要求无负环。
// 输入 n m 与 m 条边 u v w，输出最短路矩阵，不可达输出 INF。
// 点编号 1..n，要求 n < N；有限距离的绝对值小于 INF，距离相加不溢出。
// 口诀：中转点 k 最外层，两段都可达才相加。
const int N = 410;
const long long INF = 1e18;
// const long long INF = LLONG_MAX;
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); // 重边取最小；无向图还需更新 d[v][u]
    }

    for (int k = 1; k <= n; k++) // 中转点必须在最外层，内层 i、j 可以交换
        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) continue;
                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;
}

使用前面的 sample.in 运行，输出为：

1
2
3
4
5

0 3 2 5 INF
INF 0 INF 2 INF
INF 1 0 3 INF
INF INF INF 0 INF
INF INF INF INF 0

它应当与三维版本的 D[5] 完全一致。读懂三维状态、手推过层间转移之后，这段精简代码里的每一次读写就都有了依据。

9 实现时容易出错的地方

9.1 初始化、重边与无向边

全局数组默认全是零，不能直接拿来表示距离，否则会把所有点对都当作零距离可达。必须先设置对角线为零、其余为 INF，再读入边。

重边必须取最小值，不能让最后读到的一条较长边覆盖较短边。无向边需要同时更新两个方向：

1
2

d[u][v] = min(d[u][v], w);
d[v][u] = min(d[v][u], w);

9.2 两段都可达，才能相加

数学中的 $\infty$ 与负数相加仍是 $\infty$，但代码中的 INF 只是一个有限整数。若直接计算 INF + (-5)，结果小于 INF，就可能把不可达误判为可达。

所以模板先判断 d[i][k]，不可达就跳过这一行；再判断 d[k][j]，不可达就跳过当前点对。两段都可达才执行加法。

此外还要按题目范围选择数值类型与 INF：所有存储的有限距离都应与 INF 区分开，相加的中间结果也必须落在 long long 范围内。对于模板中的 $10^{18}$，若有限值的绝对值都小于它，两数相加的绝对值小于 $2\times10^{18}$，仍在 long long 范围内。

在无负环的前提下，若边权绝对值至多为 $W$，最短简单路最多有 $n-1$ 条边，可用这个界估计距离范围；取 $nW<\mathrm{INF}$ 是一个方便的充分条件（这个乘积也要用足够宽的类型计算）。INF 不是越接近整数上限越好。

9.3 不要因为某一轮没有更新就提前退出

第 $k$ 轮没有更新，只说明新开放的点 $k$ 没有带来更短路径，后面的点仍可能带来改进。本例第 $1$ 轮没有更新，但第 $2$、第 $3$ 轮都有更新。

10 负权边与负环

Floyd 的转移不依赖边权非负，因此可以处理负权边。但如果能够从 $i$ 到达一个负环，再从这个负环到达 $j$，就可以反复绕环，使 $i\to j$ 的长度无限减小，此时不存在有限的最短距离。

在数值运算不溢出的前提下，Floyd 也可以用于检测负环：运行后，如果存在点 $v$ 满足

就说明图中存在负环。因为这代表从 $v$ 出发又回到 $v$ 的负权闭合走法，其中必然含有负环；反过来，负环也会使某个对角线元素变为负数。

但“检测出负环”不等于“已经给每个点对算出答案”。若存在这样的 $v$，并且 $i\to v$、$v\to j$ 均可达，则 $(i,j)$ 的距离无下界，应按题目要求另外标记。受影响的矩阵数值不能直接当作最短距离输出。

主模板按无负环的输入使用；处理负环检测时，还需要单独保证运算范围。更多负环的背景见 负环。

11 复杂度与算法选择

• 二维模板初始化与输出需要 $O(n^2)$ 时间，读边需要 $O(m)$ 时间；核心计算为 $O(n^3)$，总时间为 $O(n^3+m)$。三维教学版打印全部 $n+1$ 层需要 $O(n^3)$ 输出时间，总时间仍为 $O(n^3+m)$。
• 三维教学版保存全部阶段，空间为 $O(n^3)$；两层滚动和二维原地更新均为 $O(n^2)$，不需要另外保存所有边。
• 预处理结束后，每次点对距离查询为 $O(1)$。

三维教学版只用于 $n\le50$ 的小图；二维模板的 N = 410 只是数组容量，不代表任意时限下都能通过。以 $n=400$ 为例，三重循环约有 $6.4\times10^7$ 次点对尝试，要结合时限判断。

12 两个延伸方向

如果需要输出具体路径，可以额外维护 nxt[i][j]，表示从 $i$ 前往 $j$ 的第一步到哪里。直接边初始化为 j；严格变短且改走 $i\to k\to j$ 时，令 nxt[i][j] = nxt[i][k]。查询时不断沿第一步前进，直到终点。不可达以及受负环影响的点对要先排除。

如果只关心能否到达，把“取最小值”换成逻辑或，把“两段长度相加”换成逻辑与，就得到传递闭包：

1
2
3
4
5

// reach[i][j] 表示是否能从 i 到达 j；先初始化自身与直接边。
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);

它沿用同一条推理：新允许经过 $k$ 后，只需考虑能否先到达 $k$，再从 $k$ 到达终点。

13 练习题目

下面按训练顺序编排，覆盖洛谷、Codeforces 和 AtCoder。先写熟全源最短路，再练习“每一轮允许哪些点作为中间点”，最后尝试改造转移。这里的分组表示训练阶段，不是各平台的官方难度。

13.1 基础巩固：求出点对距离，再使用答案

1. luogu B3647: 【模板】Floyd

给定无向连通图，输出所有点对的最短距离。适合检查初始化、重边取最小值和三重循环顺序。注意本文模板读的是有向边，本题需要同时存入两个方向。

2. luogu P2910: [USACO08OPEN] Clear And Present Danger S

要求按给定顺序经过若干岛屿，相邻的指定岛屿之间允许经过其他岛屿。先用 Floyd 求出任意两岛之间的最小危险指数，再累加指定序列中相邻两项的最短距离。注意危险指数有方向，不能擅自把矩阵改成对称的。

3. atcoder abc079_d: [ABC079D] Wall

把墙上的数字全部变成 $1$，数字之间可以经过多次转换。把 $0\sim9$ 看成十个顶点，转换费用看成有向边权，先求出每个数字转成 $1$ 的最小费用，再统计墙上的总费用；值为 $-1$ 的空格跳过。训练的是从“转换过程”中识别最短路模型。

13.2 性质与建模：理解 Floyd 的每个阶段

4. atcoder abc208_d: [ABC208D] Shortest Path Queries 2

题目要求把所有起终点、所有中间点编号上限对应的最短距离求和，恰好对应正文的 $D_k(i,j)$。每完成一整轮 $k$，再累加当前矩阵中有限的距离；不能只统计最后一轮，也不能把 INF 加进答案。总和需要 long long。

5. luogu P1119: 灾后重建

村庄按重建时间逐步开放，询问某一天两点之间的最短路。把“允许经过的中间点”从编号前缀换成“已经重建的村庄”，按时间推进 Floyd。题面保证重建时间和询问时间都不下降，还要额外检查询问的起点、终点是否已经开放；村庄编号从 $0$ 开始。

6. codeforces 295B: Greg and Graph

按给定顺序删除顶点，每次删除前统计剩余顶点之间的最短距离之和。正向删点不方便维护，可以倒过来逐个加点，每次加入一个新的中间点。更新距离时仍要枚举所有起终点，为之后的加点准备距离；统计答案时才只累加当前已加入的顶点对，最后把答案顺序还原。

13.3 综合进阶：重新建图或改变更新方式

7. atcoder abc143_e: [ABC143E] Travel by Car

汽车油箱容量有限，询问两城之间最少需要中途加油多少次。先用一次 Floyd 求路程，再把“一箱油能够到达”的不同城市连成边权为 $1$ 的新图，在新图上再跑一次 Floyd。新距离表示需要几段满油行程，起点已有满油，所以可达时加油次数比段数少 $1$。

8. codeforces 25C: Roads in Berland

给定的矩阵已经是旧路网的全源最短距离，每增加一条双向道路，就要重新统计距离之和。新增边 $(a,b,w)$ 后，变短的路径一定会使用这条边；尝试用“旧路径到 $a$、新边、从 $b$ 出发的旧路径”以及反方向更新每个点对，把每次更新控制在 $O(n^2)$。可以保存本次加边前的相关距离，按旧距离计算；统计无序点对时只枚举 $i<j$。

9. luogu P6175: 无向图的最小环问题

这是需要额外推导的扩展题：求至少包含三个顶点的最小简单环。枚举环上编号最大的点 $k$，在用 $k$ 更新距离之前，用 $i,j<k$ 且 $i<j$ 的路径拼出候选环：$d[i][j]+w[i][k]+w[k][j]$。其中 $d$ 只允许编号小于 $k$ 的中间点，$w$ 必须保留原始直接边权，不能拿已经更新过的最短距离代替。

如果时间有限，可以先做 B3647 → ABC079D → ABC208D → P1119；这条路线依次检查模板、建模、阶段状态和按时间开放中间点。

14 相关题解