Floyd 多源最短路

它回答的是另一个问题

Dijkstra 回答「从某一个起点出发，到各点多远」。 Floyd 回答的是「任意两点之间多远」—— 一次算出整张距离表。

要 V 个起点的答案，当然可以跑 V 次 Dijkstra。Floyd 的价值在于： 它用三行循环做完同一件事，而且在图稠密时反而更快（下面有实测的交叉点）。

function floyd(n, edges) {
  // d[i][j] = i 到 j 的最短距离；自己到自己是 0，其余先设为不可达
  const d = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));

  for (const [u, v, w] of edges) d[u][v] = Math.min(d[u][v], w);  // 重边取小的

  // 🚨 k 必须在最外层。为什么见下一节 —— 这是全篇唯一需要背的东西
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];

  return d;
}

⭐ k 的含义是**「只允许借道编号 < k 的点」**。外层每推进一轮，就把 k 号点 加进「可以借道」的集合里，重新审视所有点对。所以循环结束时， 所有点都可以借道 —— 那就是真正的最短路。

📌 这句话就是这份代码的全部正确性论证，也是下一节那个 bug 的根源。

🚨 k 写在最内层：两到六成的图会给出错答案

最常见的写错法，是照着「遍历所有 i、j、k」的直觉写成这样：

// ⚠️ 这是错的，对照用
for (let i = 0; i < n; i++)
  for (let j = 0; j < n; j++)
    for (let k = 0; k < n; k++)          // ← k 挪到了最内层
      if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];

错在哪：算 d[i][j] 时用到了 d[k][j]，而 k > i 时那一行还没轮到被更新， 里面装的还是直接边。于是「借道」只借到了一层，多跳的路径就漏了。

🚨 出错率不是这个 bug 的性质，是图生成器的性质。 先把口径写出来：

// n 取 5~8；每个有序对以概率 p 连边；权重取 [1, wmax] 的整数
function gen(rand, n, p, wmax) {
  const edges = [];
  for (let i = 0; i < n; i++) for (let j = 0; j < n; j++)
    if (i !== j && rand() < p) edges.push([i, j, 1 + Math.floor(rand() * wmax)]);
  return edges;
}

每档 11 个种子 × 每种子 2000 张图，报「两版结果不同的图占比」的中位数与区间：

密度 p    wmax=1（单位权）        wmax=9
0.15    21.1%  (20.2~23.8)    22.4%  (21.1~25.1)
0.20    32.7%  (30.5~35.9)    34.9%  (32.9~37.9)
0.25    41.6%  (40.4~44.1)    45.6%  (44.7~49.0)
0.30    46.9%  (43.9~49.6)    54.0%  (51.7~55.5)
0.35    47.5%  (45.0~50.3)    58.8%  (56.4~59.9)   ← 单位权那列的峰值
0.40    44.3%  (41.8~45.1)    59.9%  (57.6~62.3)
0.50    30.9%  (28.4~33.4)    59.5%  (56.6~61.1)

⭐ 两到六成，跨度三倍 —— 所以「实测 X% 的图会出错」这种说法必须带上参数。 ⚠️ 而且单位权那一列是非单调的：密度到 0.35 见顶，再密反而更不容易出错 （0.50 时只剩 30.9%）。原因是边太密时点点之间大多直连，「借道」本来就不重要 —— 这个 bug 需要图里有足够多的多跳最短路才暴露。

⭐ 但有一条与参数无关的结构性结论（44000 组图 / 191 万个点对实测）：

错版比正版小的点对    0 个

⚠️ 它不报错、不崩溃，就是安静地给一个偏大的数 —— 和 Dijkstra 撞上负权边 是同一种失败方式。偏大的幅度（p=0.35、wmax=9 那档，11 个种子）：

最坏偏大倍数     中位数 5.00×   (3.80 ~ 6.00×)     ← 极值，对采样敏感
出错的点对数     中位数 4011    (3727 ~ 4280)
其中算成不可达   中位数 2522    = 出错点对的 63%

📌 「算成不可达」是最严重的症状，它占了出错点对的六成 —— Infinity 参与后续计算会一路传染下去。

⭐ 但真正危险的不是出错率，是它「碰运气」

我本来打算举一个「4 个点的链」当反例，结果它算对了。往下试才发现：

顺向链 0→1→2→…→n-1，n = 3,4,5,6,7,8   全部两版一致，不露馅

穷举所有小图之后，最小反例是 4 个点 / 3 条边：

1→2, 2→3, 3→0        （单位权）
正确 d[1][0] = 3，k 在最内层得到 Infinity

🚨 而 n = 2 和 n = 3 时，穷举全部 4 种和 64 种边集，没有任何一种能区分两版 （这两个数就是全部：n 个点的有向边有 n(n-1) 条，边集 2^(n(n-1)) 种）。 也就是说：你拿三个点的例子手推一遍验证代码，必然通过。

⭐ 顺手把 n = 4 也穷举了：4096 种边集里 361 种能区分两版， 而边数最少的反例恰好就是上面那个 3 条边的（穷举确认，不是碰巧挑到的）。

更能说明问题的是这个 —— 把上面那个反例的节点重新编号：

原编号  1→2→3→0     ❗ 出错
重编号  0→1→2→3     两版一致，错误消失

同一张图、同一份代码，只改了节点的名字，一个错一个对。 随机图各随机重排一次编号（p=0.35、wmax=9，11 个种子 × 每种子 2000 张）：

对 → 错    中位数 275 组   (254 ~ 308)
错 → 对    中位数 286 组   (260 ~ 305)
翻转合计   中位数 28.1%    (25.9 ~ 29.7%)

⭐ 两个方向的期望值必然相同 —— 重排是双射，重排后的图分布与原分布一样， 所以「出错率」在重排前后不变，一进一出必须平衡。 ⚠️ 但逐次相等只是巧合：11 个种子里两个方向恰好相等的有 0 次。 📌 判据：「两个数正好相等」若来自随机实验，先分清是恒等式还是撞上了 —— 恒等的是期望，不是这一次的计数。

👉 所以这个 bug 的真正麻烦不是出错率高，而是它取决于输入里一个与算法无关的 偶然性质（节点碰巧怎么编号）。「我测了几个例子都对」在这里完全不构成证据。

⚖️ 我试图总结一条形状判据，失败了

看到上面那些反例，我猜规律是「最短路要借道编号比起点更大的点时才出错」， 听起来很合理。实测推翻（p=0.35、wmax=9，11 个种子取中位数）：

符合判据    3872 个点对
不符合       138 个点对        = 3.4%

反例长这样：

5→1   真实最短路 5→0→3→4→1（真值 16），k 在最内层得到 Infinity
                   ↑ 中间点 0、3、4 里没有一个比起点 5 大

⚠️ 这里先校准了观测手段再下结论：那 3.4% 会不会只是「我的路径还原代码坏了」？ 把「真值不可达 / 路径还原不出来」单独计数 —— 0 个。所以它们是真反例。 📌 3.4% 看着小，但它意味着判据会漏，而一条会漏的判据比没有判据更危险。

📌 结论只能是否定式的：没有简单的「什么形状的图会中招」。 记住位置就好 —— k 在最外层，i、j 谁在中间无所谓。

⚠️ 「多跑几遍就对了」—— 这个说法是对的

流行的补救说法：k 放内层没关系，外面再套一层多迭代几次就收敛了。 我原以为要迭代 V 轮（那就成了 O(V⁴)，纯属自找麻烦）。实测下来是常数轮 （密度 0.35、wmax=9）：

图规模	收敛所需轮数	最大
n = 8（4000 组）	1 轮 612 · 2 轮 3376 · 3 轮 12	3
n = 12（4000 组）	1 轮 29 · 2 轮 3937 · 3 轮 34	3
n = 20（2000 组）	2 轮 1960 · 3 轮 40	3
n = 40（500 组）	2 轮 484 · 3 轮 16	3
n = 80（200 组）	2 轮 200	2

所以说法成立，代价是 2~3 倍常数，不是 V 倍。

⚠️ 这里有个值得单说的教训：我第一次只跑了小样本，得到「最多 2 轮」，差点写进来。 「实测最多 K」这种上界结论对采样极其敏感 —— 它只由极少数样本决定， 而那些样本恰恰是最不容易被抽到的。 ⭐ 所以这一版把组数放大了十倍（n=8 从 400 组到 4000 组）再确认一次： 上界仍是 3 轮，没有冒出第 4 轮。 上界结论必须这样复核过才敢写。

👉 不管几轮都别这么写。把 k 挪到最外层是零成本的：同样三行，一遍就对。

Floyd 能处理负权边

这是它相对 Dijkstra 的实质优势，不只是「多源」。 沿用 Dijkstra 篇里那个反例：

0 --1--> A --5--> C
0 --2--> B --(-2)--> A

Floyd                     0→C = 5   ✅（与 Bellman-Ford 参照一致）
教科书版 Dijkstra          0→C = 6   ❌

⭐ 原因很直接：Floyd 从不「定终身」。它对每个 k 都把整张表重新审视一遍， d[i][j] 随时可以再变小。Dijkstra 的正确性恰恰建立在「弹出即最终」上， 而那需要边权非负。

负环：一行就能检测

for (let i = 0; i < n; i++) if (d[i][i] < 0) return '存在负环';

d[i][i] 的含义是「从 i 出发绕一圈回到 i」。正常情况下它应该是 0 （原地不动最划算）。小于 0 就说明存在一个绕一圈还能变便宜的环。

实测三点负环 0→1(1), 1→2(-3), 2→0(1)（环权和 −1）：

d[0][0] = -1   d[1][1] = -1   d[2][2] = -2      ← 三个点全被标出
无负环时         对角线全为 0

⚠️ 有负环时最短路本身不存在（绕环可以无限便宜），此时表里的数字没有意义， 只有「检测到了」这个事实有意义。

⭐ 什么时候用 Floyd：实测出来的交叉点

理论上 Floyd 是 O(V³)，跑 V 次 Dijkstra 是 O(V·(V+E)·log V)。 稠密图 E ≈ V² 时后者变成 O(V³ log V) —— 反而多一个 log。

🚨 耗时对照必须写清两侧的实现，否则交叉点在哪完全说不准。 下面 Dijkstra 一侧用的是 Dijkstra 篇里 dijkstra + MinHeap 的原样代码，n = 300、权重 1~9， 两边各预热一次后各跑 7 次取中位数：

密度   边数    Floyd 内层比较  Dij 边松弛   Floyd     V×Dij     谁快
0.02   1753      2.70e7        5.26e5     35.4ms    13.5ms   Dijkstra 2.61×
0.05   4563      2.70e7        1.37e6     36.6ms    22.4ms   Dijkstra 1.63×
0.08   7240      2.70e7        2.17e6     37.1ms    29.2ms   Dijkstra 1.27×
0.10   8948      2.70e7        2.68e6     36.8ms    31.0ms   Dijkstra 1.19×
0.15  13525      2.70e7        4.06e6     36.3ms    39.7ms   Floyd 1.09×   ← 交叉
0.20  18063      2.70e7        5.42e6     36.5ms    48.7ms   Floyd 1.34×
0.30  26876      2.70e7        8.06e6     36.6ms    66.2ms   Floyd 1.81×
1.00  89700      2.70e7        2.69e7     34.7ms   173.7ms   Floyd 5.00×

⭐ 前两列才是这张表的骨架，它们与实现无关： Floyd 的内层比较恒为 n³ = 2.70e7；V 次 Dijkstra 的边松弛恒为 V·E。 交叉点就是这两个量打平的地方 —— 也就是 E 涨到 n² 的某个常数倍附近。

⭐ 于是 Floyd 那一列几乎是平的（34.7~37.1 ms，极差只有 2.4 ms）： 它的耗时只由点数决定，与边数无关。稀疏图上这是劣势（白跑很多 Infinity 的格子）， 稠密图上这是优势（Dijkstra 的边松弛随边数线性涨，它不涨）。

⚠️ 交叉点落在密度 0.10 与 0.15 之间，别记成某个精确值 —— 换个堆实现（比如用 sort 冒充优先队列）它能挪到 0.3 以外。 📌 判据：报「谁更快」的表之前，先问「换一个实现这个结论会不会翻」 —— 会翻的话，就得把实现写出来，或者改报与实现无关的操作数。

👉 判据：

• 点少（V ≲ 400）且要所有点对 → Floyd，十几行，还顺带支持负权
• 点多但边稀疏 → 跑 V 次 Dijkstra
• 只要单源 → 直接 Dijkstra，别为了「一次算完」去用 O(V³)

📌 力扣上这类题的 n 基本都在 100~200，Floyd 几乎总是够用且最省事。

同一个骨架的两个变体

传递闭包 —— 只问「能不能到」，不问多远。把加法换成与、取小换成或：

for (let k = 0; k < n; k++)
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++)
      if (r[i][k] && r[k][j]) r[i][j] = true;

瓶颈路 —— 求「路径上最大边权的最小值」（比如承重最大的通路）： 把 d[i][k] + d[k][j] 换成 Math.max(d[i][k], d[k][j])，取小不变。

⭐ 三者的骨架完全一样，变的只是「怎么把两段拼起来」和「怎么算更好」。 这就是把 Floyd 记牢的最省力方式：记那三层循环的顺序，剩下的是填空。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

• 1334. 阈值距离内邻居最少的城市中等⭐ Floyd 裸题：n ≤ 100，先求全源距离表再逐点数
• 1462. 课程表 IV中等传递闭包：把加法换成与、取小换成或，骨架不动
• 399. 除法求值中等带权闭包：把「相加」换成「相乘」，Floyd 照样成立
• 2101. 引爆最多的炸弹中等先建可达图再求闭包；⚠️ 引爆关系是单向的，别建成无向
• 1697. 检查边长度限制的路径是否存在困难瓶颈路：拼接改成 Math.max。⚠️ n 到 1e5，这题只能并查集，用来体会 Floyd 的规模上限
• 743. 网络延迟时间中等Dijkstra 篇练过；这次用 Floyd 写一遍，n ≤ 100 完全够

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。