一次性算出图中任意两点之间的最短距离——三重循环，本质上是一个动态规划，思路和 13 模块的框架完全相通。
14.1、14.4 节的 BFS、A* 解决的都是"从一个起点出发，到某个终点（或所有点）的最短路"——这类问题统称单源最短路。但有些场景需要知道任意两点之间的最短距离（比如"任意两个城市之间开车最快多久能到"），如果对每个点都单独跑一次单源最短路，需要跑 V 次。Floyd 算法能用一次性的三重循环，直接算出所有点对之间的最短距离，代价是要求图的规模不能太大（见 ⑤）。
Floyd 算法看起来只是三层 for 循环，但它的本质是一个动态规划——用的正是 13 模块讲过的那套框架。设 dp[k][i][j] 表示：只允许经过编号 1~k 的点作为中转站时，i 到 j 的最短距离。
| 要素 | Floyd 算法里对应什么 |
|---|---|
| 状态定义 | dp[k][i][j]：只允许经过 1~k 号点中转时，i 到 j 的最短距离 |
| 转移方程 | dp[k][i][j] = min( dp[k-1][i][j]， dp[k-1][i][k] + dp[k-1][k][j] ) |
| 初始化 | dp[0][i][j] = 原图中 i、j 之间直接的边权（没有边就是 INF），dp[0][i][i]=0 |
| 填表顺序 | k 从 1 到 n 依次增大（第几个中转点被"解锁"） |
转移方程的含义很直白：i 到 j，允许经过 1~k 号点中转时的最短距离，要么压根不经过 k 号点（沿用 dp[k-1][i][j]），要么经过 k 号点中转（先从 i 到 k，再从 k 到 j，两段都只用 1~k-1 号点中转），取两者较小的一个。
dp[k][*][*] 只需要用到 dp[k-1][*][*]——和 13.2 节背包问题"压缩成一维数组"是同样的道理，这里可以把"第几轮中转点"这一维原地滚动，直接在同一个二维数组 dist[i][j] 上更新，不需要真的开一个三维数组。这也是为什么 Floyd 算法最终代码看起来只是"三层循环 + 一行 min"，背后其实是省略了一维的动态规划。沿用 15.1 节的示例图（顶点 A B C D，边 A-B=4，A-C=1，B-C=2，B-D=5，C-D=8），初始的邻接矩阵（INF 表示没有直接的边）：
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 4 | 1 | ∞ |
| B | 4 | 0 | 2 | 5 |
| C | 1 | 2 | 0 | 8 |
| D | ∞ | 5 | 8 | 0 |
A、D 之间没有直接的边，暂时是 ∞（不可达）。接下来依次让 A、B、C、D 轮流当"中转点"，看看能不能借道缩短某些距离。| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 4 | 1 | 9 |
| B | 4 | 0 | 2 | 5 |
| C | 1 | 2 | 0 | 7 |
| D | 9 | 5 | 7 | 0 |
A→D 原本是 ∞，经过 B 中转 A→B→D = 4+5 = 9，比 ∞ 小，更新为 9；C→D 原本是 8，经过 B 中转 C→B→D = 2+5 = 7，比 8 小，更新为 7。| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 3 | 1 | 8 |
| B | 3 | 0 | 2 | 5 |
| C | 1 | 2 | 0 | 7 |
| D | 8 | 5 | 7 | 0 |
A→B 原本是 4，经过 C 中转 A→C→B = 1+2 = 3，更新为 3；A→D 上一轮刚更新成 9，这一轮经过 C 中转 A→C→D = 1+7 = 8（这里用的 C→D=7 是上一轮 B 中转之后的最新值），比 9 更小，再次更新为 8。之后再让 A、D 当中转点检查一遍，矩阵不再变化——最终 A 到 D 的最短距离是 8，对应路径 A→C→B→D（1+2+5=8）。A→D 被更新了两次：第一次借道 B 从"不可达"降到 9，第二次借道 C（这时候 C→D 已经是借道 B 优化过的 7）又降到 8。这正体现了动态规划"状态转移建立在之前已经算好的结果之上"——dp[k][i][j] 依赖的 dp[k-1][i][k]、dp[k-1][k][j]，本身也可能是前面几轮中转优化过的结果，中转点的效果会像滚雪球一样累积。| 1 | const int INF = 0x3f3f3f3f; |
| 2 | int dist[MAXN][MAXN], n; // dist[i][j]：15.1 节邻接矩阵初始化后，就是 dp[0][i][j] |
| 3 | |
| 4 | void Floyd() |
| 5 | { |
| 6 | for (int k = 1; k <= n; k++) // ★ k（中转点）必须放在最外层，见 ⑥ 陷阱 |
| 7 | for (int i = 1; i <= n; i++) |
| 8 | for (int j = 1; j <= n; j++) |
| 9 | dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); |
| 10 | } |
k 对应 dp 的"第几轮中转点"这一维（已经被压缩省略，直接原地滚动更新 dist）；第 7、8 行的 i、j 枚举所有点对；第 9 行就是转移方程本身——dist[i][j]（不经过 k）和 dist[i][k] + dist[k][j]（经过 k 中转）取较小值。循环结束后，dist[i][j] 就是 i 到 j 的最短距离。三层循环，每层都是 O(n)，总时间复杂度 O(n³)；空间上只需要一个 n×n 的矩阵，O(n²)。
| 点数 n | O(n³) 大致运算量 | 是否适合用 Floyd |
|---|---|---|
| 100 | 约 100 万 | 非常适合，毫秒级完成 |
| 1,000 | 约 10 亿 | 勉强可以，但接近超时边界 |
| 10,000 | 约 1 万亿 | 不适合，会严重超时 |
dp[k] 这一轮时，dp[k-1] 必须已经完全算好"，也就是说必须先把 k=1 这一轮的所有 i、j 都更新完，再进入 k=2。如果把 k 放在最内层循环，会在"上一个中转点还没枚举完所有点对"的情况下就提前使用了还没更新完整的数据，算出来的最短路可能是错的（哪怕看起来数值上"差不多"，某些点对的结果会不正确）。INF，不能用 0。dist[i][k] + dist[k][j]，如果 i、k 和 k、j 都不连通，两边都是 INF，相加会超过 int 能表示的范围，溢出后可能变成一个很小甚至负数的值，被误判成"更短的路径"。解决办法是把 INF 取一个"足够大，但加两次也不会溢出"的值（比如 0x3f3f3f3f 而不是 INT_MAX），这也是本节代码里 INF 取这个特定数值的原因。dist[i][i]，如果某个 dist[i][i] < 0，说明存在经过 i 的负权环。O(n³)、只能应付较小的图。15.3 节的 Dijkstra 会回到"单源最短路"这个更常见的问题，用贪心 + 优先队列把复杂度降到 O((V+E) log V)，能处理大得多的图。