🏁

Floyd：中间人接力

「任意两点之间最短路是多少？」——不止一个起点！Floyd 的招数：中间人名单从「只许 1 号」逐步放宽到「谁都能当」，每放宽一个人，就把所有「能经他绕近路」的点对更新一遍。

💡 打个比方

上次 Dijkstra 只答「一个起点到所有点」的最短路（水波纹）。今天的问题更大：任意两点之间的最短路都要——5 个点就有 5×4 = 20 个「点到点」的问题，难道跑 5 遍 Dijkstra？能跑，但 Floyd 有更聪明的接力赛玩法。

想象一个 4 个点的地图，我们规定：「中间人」只能从 1..k 号里选，k 从 1 一步步放到 4。 k=1 时，路线只许「最多经过 1 号」；k=2 时，1、2 号都可以当中间人；k=3、k=4 类推。每放宽一个新人 k 加入，就问一遍所有点对 (i, j)：「i → k → j」比现在的记录 dist[i][j] 更短吗？是就更新。 关键洞察：当 k 走到 n，所有点都当过中间人，dist 表里装的就是任意两点最短路。为什么「逐步放宽」不会漏？因为任意一条最短路，它的中间点集合一定包含在 1..n 里——k 数到那个「编号最大的中间点」时，这条路就已经被考虑过了。

核心公式（每轮对每个点对做一次）：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])——「旧记录」与「经 k 中转」取小的。和 Dijkstra 的松弛一个味儿，只是 Dijkstra 每轮定一个点，Floyd 每轮放宽一个中间人、扫全部点对。

代价呢？k 走 n 轮，每轮 n×n 个点对——O(n³)。n = 100：100 万步，眨眼完成；n = 1000：10 亿步，秒级就悬了——大图的「任意两点」问题要么跑 n 遍 Dijkstra，要么上更高级的算法。Floyd 的甜区是n 不大（≤ 几百）+ 要全表 + 边权可以为负（只要没有负环）。

术语：全源最短路（所有点对之间的最短距离，一张 n×n 的 dist 表）；中间人 / 中转点（路线允许经过的点）；Floyd–Warshall（本算法，也简称 Floyd）；O(n³)（n 轮 × 每轮 n² 个点对）；负环（绕一圈总权 < 0 的圈——绕得越久越短，最短路不存在，Floyd 也会算错）。

🖼️ 大图看明白

🧩 子任务 1：单源 vs 全源——问的问题不一样

🎯 小目标：分清 Dijkstra 和 Floyd 各答什么问题；算出「全源」要答多少对。

// 同一个 4 点图（造价：1-2=3, 1-3=6, 2-3=2, 3-4=4）

// ── 单源最短路（Dijkstra）──
// 问：从「一个」起点出发，到每个点的最短路
// 例：起点 = 1 → 1→2=3，1→3=5（经 2），1→4=9（经 2、3）
// 只有一行答案——换个起点就得从头再跑一遍

// ── 全源最短路（Floyd）──
// 问：「任意」两点之间的最短路——一张 n×n 的大表
// 4 个点：4×3 = 12 个「有序」点对（1→2 和 2→1 算两个问题）
// 本图无向（桥双向），对称：1→2 = 2→1，实际只需算 4×3÷2 = 6 对
// 完整答案（先记住，后面用 Floyd 手推验证）：
//   1→2=3   1→3=5   1→4=9
//   2→3=2   2→4=6（经 3）
//   3→4=4

✅ 小检查：① 起点 1 的 Dijkstra 答哪几个数？② 4 个点的全源问题要答多少个「有序」点对？③ 用 Dijkstra 拿全表要跑几遍？

看看答案

① 1→2=3、1→3=5、1→4=9（1→4 必须经 3：3+2+4 = 9，没有别的桥）。② 4×3 = 12 个有序点对（无向图对称，实际算 6 对即可）。③ n = 4 遍——每个点当一次起点。每遍 Dijkstra（邻接矩阵版）O(n²)，4 遍共 O(n³)，和 Floyd 同阶——所以「要全表」时，Floyd 跑一遍反而更省事（代码只有三层循环，不用换起点）。

易错：以为「跑一遍 Dijkstra 就能得到全表」——水波纹从一个点荡开，荡到的都是「从那个点出发」的距离；起点换人，波纹要重新扔石子。

🧩 子任务 2：Floyd 的思想——中间人白名单

🎯 小目标：搞懂「第 k 步 = 只许 1..k 当中间人」的规则，和更新公式 dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])。

// 规则：第 k 步时，路线「中间点」只许从 {1, 2, ..., k} 里选
//（端点 i、j 自己不算中间点；k 从 0 放到 n，每放一个人，表更新一轮）

// dist[i][j] 在第 k 步的含义 = 「中间点只许 1..k」时 i 到 j 的最短路

// ── 初始表（k = 0：只许走直达桥，不许任何中间人）──
//        到1   到2   到3   到4
//   从1    0     3     6    ∞
//   从2    3     0     2    ∞
//   从3    6     2     0     4
//   从4    ∞     ∞     4     0
// 没桥 = ∞（不是 0！）；「到自己」= 0

// ── 每放一个新中间人 k，对每一对 (i, j) 问一遍 ──
//   新路 = dist[i][k] + dist[k][j]   「先去 k，再从 k 去 j」
//   如果 新路 < dist[i][j]，就更新（更便宜才换）

// 为什么 k 放到 n 就全对？任何一条路的中间点编号都在 1..n 里，
// 当 k = 那条路「编号最大的中间点」时，它就已经被拿来比过了。

✅ 小检查：① 第 k=1 步，dist[2][4] 表示什么？值是多少？② 初始表里「到自己」为什么是 0？③ 更新公式里「dist[i][k] + dist[k][j]」的两段分别是什么？

看看答案

① 「只许 1 当中间人」时 2→4 的最短路 = min(直达 ∞, 2→1 + 1→4 = 3 + ∞) = ∞——1 是端点，经它绕不出新路。② 点到自己距离 0——没有它，「i 经 k」当 i = k 时就断了（dist[k][k] 必须是 0，「原地不动」才算数）。③ 两段都是上一轮表里的最短路：「i 先走到 k」+「k 再走到 j」。拼起来 = 一条「最大中间点是 k」的候选路；更便宜就换记录。

易错：两个大坑。① 「没桥」写成 0——0 意味着「免费直达」，全表瞬间塌方；没桥写 ∞（一个足够大的数，如 999999）。② 循环顺序乱写——k 必须在最外层（for k → for i → for j），否则「两段」里可能混进已经用了 k 的新值，「白名单只许 1..k」的含义就被破坏了。

🧩 子任务 3：手推——4 点图，k 从 1 走到 4

🎯 小目标：亲手把 Floyd 的每一轮 dist 表推出来，看「哪些格子变了、什么时候变」。

// 4 点图：1-2=3, 1-3=6, 2-3=2, 3-4=4（没桥 = ∞）

// ── 初始（k=0，只许直达）──
//       到1  到2  到3  到4
//   从1   0    3    6   ∞
//   从2   3    0    2   ∞
//   从3   6    2    0    4
//   从4   ∞    ∞    4    0

// ── k=1（只许 1 当中间人）：无变化 ──
// 经 1 试一圈：2→1+1→4 = 3+∞ = ∞，3→1+1→4 = 6+∞ = ∞ ……
// 1 是端点、又没有 1-4 的桥，经它绕不出任何更短的路。

// ── k=2（1、2 可当中间人）：2 个格子变了 ──
//       到1  到2  到3  到4
//   从1   0    3    5   ∞    ← 1→3：3+2 = 5 < 6，经 2 便宜！
//   从2   3    0    2   ∞    （2→4：3+∞ 还是 ∞，2 通不了 4）
//   从3   5    2    0    4    ← 3→1 对称地变成 5
//   从4   ∞    ∞    4    0

// ── k=3（1、2、3 可当中间人）：4 个格子变了 ──
//       到1  到2  到3  到4
//   从1   0    3    5    9    ← 1→4：5+4 = 9，通了！(1→2→3→4)
//   从2   3    0    2    6    ← 2→4：2+4 = 6，通了！(2→3→4)
//   从3   5    2    0    4
//   从4   9    6    4    0    ← 4→1 = 9、4→2 = 6（对称）

// ── k=4（谁都能当中间人）：无变化 ──
// 经 4 试一圈：1→4+4→2 = 9+6 = 15 > 3，只会绕更远（非负权绕远只加不减）。
// k 走满 n = 4，收工。最终表 = k=3 那张表。

✅ 小检查：① dist[1][4] 第一次变出有限数是在第几步？② k=2 之后，1→3 是多少、经谁？③ 为什么 k=4 一步没有任何变化？

看看答案

① k=3——3 进白名单的那一刻，「1→2→3→4」这条路（3+2+4 = 9）第一次被拼出来：dist[1][3](=5) + dist[3][4](=4) = 9。② 5，经 2：3+2 = 5 < 6（直达的 6 被淘汰）。③ 4 是端点：「经 4」= 先绕到 4 再回头，非负权下只多不少——所以尽头点当中间人永远是白工。注意：不是每步都有变化，k=1、k=4 都是原封不动；表只可能变短、不可能变长（每次更新都是 min）。

易错：手推时「顺手」用本轮刚更新的值去更新别的格子——例如 k=3 时刚把 dist[1][4] 改成 9，又拿这个 9 去更新 dist[1][2]。严格做法：一轮里所有计算都用「上一轮结束时的表」（代码里 k 在最外层、i/j 在内层，天然满足）。

🧩 子任务 4：O(n³) 有多快？何时换 Dijkstra？

🎯 小目标：会算 Floyd 的步数 n³，会按「要几对、n 多大、有没有负权」选工具。

// Floyd 步数 = n(k) × n(i) × n(j) = n³
//   n = 50   → 50³   =    125,000   步   眨眼
//   n = 100  → 100³  =  1,000,000   步   眨眼
//   n = 300  → 300³  =  27,000,000   步   几秒
//   n = 1000 → 1000³ = 1,000,000,000 步   十亿步，太慢！

// 对照：要全表，跑 n 遍 Dijkstra（矩阵版每遍 O(n²)）= n × n² = n³
// 同阶！所以「要全表」时两者速度相当，Floyd 代码更短（三层循环，不用换起点）

// 选工具口诀：
// ① 只要「一个点」到所有点 → Dijkstra（O(n²)，比 n³ 快一个 n 倍）
// ② 要「任意两点」全表、n ≤ 几百 → Floyd
// ③ 要全表、n 很大（上千）→ n 遍 Dijkstra（配优先队列更快）
// ④ 边权有负的（没有负环）→ 只有 Floyd 能上（Dijkstra 怕负权！）

✅ 小检查：① n = 500，Floyd 约多少步？② 只要 1 号到所有点、n = 1000，选谁？③ 图里有一条权为 −2 的边（无负环），要全表，选谁？

看看答案

① 500³ = 125,000,000（1.25 亿）步——临界地带，简单实现可能要几秒。② Dijkstra——只要单源，O(n²) = 1,000,000 步（矩阵版），比 n³ = 10 亿步少 1000 倍。③ Floyd——有负权，Dijkstra 的「盖章定案」会翻车（上上节课 −5 的反例），Floyd 不盖章、只比较，负权（无负环）照样对。

易错：① 1000³ 常少算一个零写成 1 亿——1000³ = 1,000,000,000 = 10 亿（1000 × 1000 × 1000，三个 1000 连乘）。② 「图的问题就 Dijkstra」——它只对一个起点省钱，而且怕负权；全表 + 负权 = Floyd 的主场。

💻 完整代码：Floyd（5 点）→ 输出全源最短路表 + 指定两点

// 输入：无（5 岛 7 桥写死，方便对答案）
// 输出：任意两点最短路全表 + 2 到 5 的最短距离
// 答案：2→5 = 10（经 1：2+8，比经 4 的 7+5 = 12 便宜）
#include <iostream>
using namespace std;

int g[6][6];      // 邻接矩阵：g[i][j] = 桥造价，0 = 没桥
int dist_[6][6];  // dist_[i][j] = i 到 j 的当前最短路（全源大表）

int main() {
    // 5 岛 7 桥：1-2:2  2-3:3  3-4:4  4-5:5  1-3:6  2-4:7  1-5:8
    g[1][2] = g[2][1] = 2;  g[2][3] = g[3][2] = 3;
    g[3][4] = g[4][3] = 4;  g[4][5] = g[5][4] = 5;
    g[1][3] = g[3][1] = 6;  g[2][4] = g[4][2] = 7;
    g[1][5] = g[5][1] = 8;

    const int INF = 999999;
    // 初始化：到自己 = 0；有桥 = 桥造价；没桥 = ∞
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            dist_[i][j] = (i == j) ? 0 : (g[i][j] > 0 ? g[i][j] : INF);

    // Floyd 三层循环：k 必须最外层！（中间人白名单逐步放宽）
    for (int k = 1; k <= 5; k++)          // 让 k 加入中间人名单
        for (int i = 1; i <= 5; i++)      // 起点
            for (int j = 1; j <= 5; j++)  // 终点
                if (dist_[i][k] + dist_[k][j] < dist_[i][j])
                    dist_[i][j] = dist_[i][k] + dist_[k][j];

    // 输出全表（行 = 从 i 出发，列 = 到 j）
    for (int i = 1; i <= 5; i++) {
        cout << i << ": ";
        for (int j = 1; j <= 5; j++)
            cout << dist_[i][j] << " ";
        cout << endl;
    }
    cout << "2 到 5 最短距离 = " << dist_[2][5] << endl;
    return 0;
}
// 运行结果：
// 1: 0 2 5 9 8
// 2: 2 0 3 7 10
// 3: 5 3 0 4 9
// 4: 9 7 4 0 5
// 5: 8 10 9 5 0
// 2 到 5 最短距离 = 10
// 对照 Dijkstra：第 1 行（0 2 5 9 8）和 Dijkstra 从 1 出发的答案完全一致 ✓
// 把 g[1][5] 改成 20：1→5 = 14（经 1-2-4-5），2→5 = 12（经 2-4-5）

✋ 你来试试

第 1 题：5 点图里，1→4 的最短路是多少？有两条一样短的路吗？

9，有两条：1→2→4 = 2+7 = 9，和 1→2→3→4 = 2+3+4 = 9——正好打平。Floyd 只记距离不记路，所以表里就是 9；「两条一样短」这种信息它不保存（想保存得加记录表，见第 3 题）。

第 2 题：把 1-5 桥造价改成 20，1→5 和 2→5 各是多少？

1→5：直达 20 太贵了；经 2：2 + (2→5)。先算 2→5：经 1 = 2+20 = 22 更贵，经 4 = 7+5 = 12 → 2→5 = 12。所以 1→5 = min(20, 2+12 = 14, …) = 14（走 1→2→4→5）。一改价，「免费高速」1-5 立刻出局，全表跟着重算——这就是全源表的威力：一次跑完，所有点对都更新了。

第 3 题：想让程序输出「1→2→4→5」这样的路线，要加什么表？和 Dijkstra 的 prev 一样吗？

加一张 via[i][j] 表：每次用 k 更新 dist[i][j] 成功时，记 via[i][j] = k（「i 到 j 最短路经 k」）。但和 Dijkstra 的 prev 不一样：Dijkstra 的 prev 是一条链（目标 → 前驱 → … → 起点），Floyd 的 via 是递归拆三段——path(i, j) = path(i, via[i][j]) + path(via[i][j], j)，拆到 via 为空（直达桥）为止。像「1 到 5 经 2；2 到 5 经 4；1 到 4 经 3……」一层层拆，最后拼成完整路线。

第 4 题（加餐）：图里如果有一个「负环」（绕一圈总造价 < 0），Floyd 跑完怎么发现它？

看对角线：dist[i][i] 本来是 0（自己到自己）；如果有负环，绕一圈回到自己反而更便宜，dist[i][i] 会被更新成负数。所以 Floyd 跑完扫一遍对角线：只要某个 dist[i][i] < 0，就说明存在负环——那时「最短路」根本不存在（绕得圈数越多越短），表里的数也不能全信。

🎯 一句话记住：Floyd = 中间人接力——k 从 1 走到 n，每轮「让 k 进中间人白名单 + 更新所有点对 dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])」，k 必须最外层；O(n³)：要全表且 n 不大、或边权可为负（无负环）→ Floyd，只要单源 → Dijkstra；本课答案：4 点图 1→4=9、2→4=6，5 点图 2→5=10（经 1）。

← 上一课：10 Dijkstra 最短路下一课：12 图论工具箱 →