大学图论第 4 讲：最短路三件套——Dijkstra 为什么怕负权，Floyd 的三重循环凭什么正确-育师

大家好，我是熊猫钓鱼，欢迎大家点赞关注！

《把定理跑出来》系列第 4 讲。最短路是图论课的绝对核心，也是考研计算题的最大的题源。Dijkstra、Bellman-Ford、Floyd 三个名字背得滚瓜烂熟，但"为什么一个怕负权、一个不怕、一个连负环都能查"——背是背不出来的，跑一遍就懂了。
本讲 8 张图全部由文末代码生成，种子固定（SEED=2026），可复现。所有算法均为手写课本实现，两两对拍。

摘要

Dijkstra 负权失效实测：4 顶点反例（0→1 权 1、0→2 权 2、2→1 权−2、1→3 权 1）上，课本版 Dijkstra 给出 dist[3]=2.0，真最优是1.0（0→2→1→3）——误差 100%，且毫无报警；
对拍边界：正权随机图200 组零分歧；87 组含负权（无负环）图上，"允许重访"的堆版 Dijkstra意外全部答对——但同一实现在含负环的图上直接死循环 8 分钟（调试实录），dist 沿负环每圈递减、堆无限膨胀；
Bellman-Ford 早停：随机图实际收敛轮数 5.3~6.7 轮，远小于理论上限 V−1（49~399 轮）——但复杂度仍按最坏算；
Floyd 的 k：k 轮 = 只允许中转点 {0…k−1} 的最短路，5 联热图逐轮演示 ∞ 消失与数值下降；Floyd vs 逐源 Dijkstra 60 组对拍零分歧，路径重建（next 矩阵）与 prev 树重建30/30代价一致；
规模横评：稠密图 n=400——Dijkstra 1.84ms、Bellman-Ford 10.03ms、Floyd2155ms；稀疏图上 Bellman-Ford 只比 Dijkstra 慢约 2 倍——O(VE) 与 O((n+e)logn) 的理论差距被常数吃掉（第 3 篇的教训再次应验）；
负环检测：Floyd（对角线变负）与 Bellman-Ford（第 V 轮仍可松弛）两个独立实现的检测器在负环 fixture 上结论一致。

关键词：Dijkstra；Bellman-Ford；Floyd；负权边；负环；松弛；动态规划；路径重建；复杂度实测

1. 三件套的一句话分工
2. Dijkstra 怕负权：课本反例实测
- 2.1 三层真相：课本版错、堆版侥幸、负环必死
- 2.2 对拍：正确性的边界就是"非负"两字
3. Bellman-Ford：允许"后悔"的算法
- 3.1 实际轮数远小于 V−1
4. 负环检测：两个检测器互相校验
5. Floyd：三重循环凭什么正确
6. 规模横评：两条 n³ 的曲线与一条 n² 的曲线
7. 选型元图
8. 本讲检查清单
9. 复现指南
10. 下一讲预告

1. 三件套的一句话分工

先给结论版的地图，后面的实验负责让这张地图"长出来"：

Dijkstra：贪心。前提"边权非负"，单源最快；
Bellman-Ford：动态规划式的反复松弛。允许负权、能查负环，代价 O(VE)；
Floyd：动态规划。一次算出所有点对的最短路，O(n³) 换 10 行代码。

2. Dijkstra 怕负权：课本反例实测

图 1：课本经典反例。边 0→1 权 1、0→2 权 2、2→1 权−2、1→3 权 1。Dijkstra 的贪心顺序是：确定 1（dist=1）→ 确定 2（dist=2）→ 2 的松弛想把 1 更新为 2−2=0——但 1 已经"确定"，更新被永久关闭。最终 dist[3]=2.0，真最优 1.0（0→2→1→3），误差 100% 且毫无报警。

2.1 三层真相：课本版错、堆版侥幸、负环必死

做这个实验时我踩了一脚真实的坑， worth 单独一节。第一版反例图构造不对，堆版 Dijkstra 居然算对了——追查后发现一个课本不讲的三层结构：

课本版（确定后不再更新）：负权边即错。图 1 实测 dist[3]=2.0 vs 真值 1.0；
允许重访的堆版（dist[v]更小就再入堆、弹出时已过期则跳过）：负权边的改进还能传播。87 组含负权的随机图实测全部答对——但这是"意外正确"：每次改进都重新入堆，复杂度退化无上界；
含负环的图：dist 沿负环每绕一圈递减，堆无限膨胀——死循环。调试本讲实验时，一个含负环的随机测试图让程序挂了 8 分钟，进程杀掉才解脱。

所以"Dijkstra 为什么怕负权"的完整答案分三层：课本实现给错答案；堆实现靠重访侥幸给对但复杂度失控；遇到负环则连"答案"这个概念都不存在。三层对应三种工程后果：错误结果、超时、挂死——一层比一层疼。

2.2 对拍：正确性的边界就是"非负"两字

图 2：左：正权随机图 200 组，Dijkstra 与 Bellman-Ford 距离向量零分歧（注意：不连通时双方都是 INF，abs(INF−INF)是 NaN 会悄悄破坏比较——对拍代码必须先做相等性判断，这是本讲调试时踩的第二个坑）；右：87 组含负权（无负环）图，堆版全对——但别用它，理由见 2.1 第 3 层。

3. Bellman-Ford：允许"后悔"的算法

课本原话：对所有边做 V−1 轮松弛，任何"晚到的更优解"都有机会传播。第 V 轮仍可松弛 ⟺ 存在负环。

图 3：随机图上 Bellman-Ford 的实际收敛轮数。n=50~400 时均值 5.3~6.7 轮、最大 10 轮——远小于理论上限 V−1（49~399）。红菱形是理论上限，和蓝柱之间隔着一个数量级。

这正是早停的价值：changed标志一置 False 就收工，随机图上几乎总是几轮结束。但复杂度报价仍按最坏 O(VE)——随机图的友好不能当饭吃，第 6 节的横评会看到它最坏时的样子。

3.1 实际轮数远小于 V−1

Bellman-Ford 的另一个身份是负环检测器：第 V 轮仍可松弛 ⟺ 负环存在。第 4 节用 fixture 验证过它的报警功能。

4. 负环检测：两个检测器互相校验

负环一旦存在，"最短路"这个概念就死了（绕一圈便宜一次，可以无限刷）。检测它有两套独立思路：

Bellman-Ford：第 V 轮仍能松弛；
Floyd：跑完后对角线dist[i][i] < 0。

图 4：负环 fixture（0→1→2→0 总权 −1）。Floyd 的对角线变负（[−1, −1, −2]），Bellman-Ford 第 V 轮仍可松弛——两个独立实现的检测器结论一致。检测器本身也要用 fixture 验证"真的会响"，这一原则贯穿整个系列。

5. 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])，滚动数组压掉一维就是课本那三重循环。

"k 的含义"是这一节唯一需要真正理解的东西。我们直接把每一轮的 dist 矩阵拍下来：

图 5：n=5 的五联热图。k=1：允许中转 0 号点，部分 ∞ 消失；k=2、k=3 继续改善（红色标题）；k=4 一轮无变化（灰色——该点带来的改进已被前面覆盖）；k=5 又有改善。每过一轮，图就"解锁"一个新中转点——这就是 k 的全部含义，动态规划的正确性一眼可见。

正确性对拍：Floyd 与逐源 Dijkstra60 组随机图零分歧；next 矩阵重建的路径与 Dijkstra prev 树重建的路径30/30 对总代价一致（第一版对拍只有 7/30——next 更新写成了nxt[k][j]，标准写法是nxt[i][k]，即"i→k 路径的第一步"；一个下标写错，路径重建就废了）。

6. 规模横评：两条 n³ 的曲线与一条 n² 的曲线

图 6：稠密图（m≈n²/4）单源耗时。n=400：Dijkstra 1.84ms、Bellman-Ford 10.03ms、Floyd2155ms。注意口径——Floyd 算的是全源，Dijkstra 只是单源；但即使 n 次 Dijkstra 全源（≈0.7s）也快过 Floyd（2.2s）。Floyd 赢的不是速度，是 10 行代码、是全源一步到位、是免费附赠的负环检测。

图 7：稀疏图（m=6n）上 Dijkstra vs Bellman-Ford。n=800：0.95ms vs 1.95ms——BF 只慢约 2 倍。O(VE) 与 O((n+e)logn) 的理论差距该有几十倍，但 BF 内层是纯数组扫描、堆却是 Python 对象——第 3 篇"复杂度≠性能"的教训在稀疏图上再次应验。

7. 选型元图

图 8：先问四个问题——负权？稠密？全源？负环？依次映射到三件套，负环直接判"不存在"。

8. 本讲检查清单

□ Dijkstra 怕负权的完整答案？（课本版给错答案；堆版靠重访侥幸对但复杂度失控；负环挂死） □ Dijkstra 正确性的前提？（边权非负——200 组正权对拍零分歧） □ Bellman-Ford 实际几轮收敛？（随机图 5~7 轮，但复杂度按 O(VE) 报价） □ 负环怎么查？（BF 第 V 轮仍松弛 / Floyd 对角线变负，两法独立且一致） □ Floyd 的 k 是什么？（只允许中转 {0..k−1} 的最短路——图 5 的五联热图） □ Floyd 的 next 矩阵怎么更新？（nxt[i][j] = nxt[i][k]，不是 nxt[k][j]！） □ 稠密/稀疏图怎么选？（稠密单源 Dijkstra；全源看场景——Floyd 代码最短还送负环检测）

9. 复现指南

graph-course/ ├── course4.py # 六组实验（反例/对拍/轮数/k 演化/横评/负环，~330 行） ├── figs4.py # 8 张配图 ├── results/course4.json └── figures/

python course4.py# → results/course4.json（约 2 分钟）python figs4.py# → 8 张图

正确性断言：正权对拍 200 组零分歧（含 INF 相等性兜底）；Floyd 与逐源 Dijkstra 60 组零分歧；路径重建双方法 30/30 代价一致；负环 fixture 双检测器一致；负权组先跑 BF 判负环再跑 Dijkstra——顺序不能反，堆版 Dijkstra 遇负环会死循环（8 分钟的教训）。