图系列第 10 篇：Bellman-Ford 与负环

嘿，朋友，欢迎回到图系列。这是第 10 篇，我们要正面解决一个从第 8 篇起就被反复预告的“心结”——负权边。前两篇里，Dijkstra 表现得又帅又稳：在非负权图上，每次挑一个“当前距离最小”的顶点定案，用堆优化后 O((V+E) log V) 就能算出单源最短路。但我们每次都刻意强调同一句话：它怕负权。为什么怕？因为那条漂亮的贪心证明里，“后续边权非负”是命门；一旦出现负数，整个“先定案就不再改”的策略就会崩盘。今天的主角 Bellman-Ford 就是来收拾这个烂摊子的：它不挑顺序、不搞贪心，只是把全图所有边“刷”一遍又一遍，刷满 V−1 轮，负权照样能算；再多刷一轮，还能把隐藏的负环揪出来。

这篇的长途路线图如下：先回顾 Dijkstra 的负权反例，把“负权为什么难”这件事钉死；然后隆重介绍松弛操作——所有最短路算法的发动机，顺便讲讲它为什么叫“松弛”；接着用“最短路径最多 V−1 条边”这个关键事实，解释为什么 Bellman-Ford 刷 V−1 轮就够；再用手算完整走查一张带负权的图，看 dist 表一轮一轮收敛；之后给出 JS/TS 边集实现并逐行解释；再进入重头戏——负环检测：第 V 轮还能松弛意味着什么，负环为什么让“最短路径”失去意义；随后用一节快速认识 SPFA 这个队列优化版；再聊外汇套利、差分约束等经典应用；最后做一张算法选型速查表、附上自测题和下一篇预告。准备好了吗？我们从“负权为什么难”开始。

1 回顾：Dijkstra 的负权反例，以及负权为什么难

1.1 前两篇留下的结论

第 8 篇我们从 BFS 出发，解决了无权图的最短路径；第 9 篇把“每条边代价都是 1”的假设放宽成“边权非负”，得到了 Dijkstra。Dijkstra 的骨架大家应该已经很熟：初始化 dist 数组，起点为 0，其余为无穷大；每一轮从“未确定”的顶点里挑出 dist 最小的那个，宣布它定案；然后松弛它的所有出边，尝试刷新邻居的距离；重复直到所有可达顶点都定案。这套流程里最重要的数据结构是优先队列，最重要的操作是松弛，最重要的正确性依据是“非负权”。

为什么非负权如此关键？回忆第 9 篇的证明：假设算法准备把顶点 u 定案，此时 u 是未确定集合里 dist 最小的。若存在一条真实更短的路径到达 u，这条路径必然在某处从“已确定区域”跨到“未确定区域”，跨过一条边 (x, y)。由于边权非负，路径后续部分只会让总代价增加，所以任何替代路径都不可能打败 u 当前的 dist。证明里的核心不等式是“路径总代价 ≥ 前缀代价”，而它成立的前提，恰恰是“每一条后续边的权重都 ≥ 0”。换句话说，Dijkstra 的贪心不是万能的，它把“越走越贵”当成天经地义——一旦有一条边是负的，这个天经地义就不成立了。

1.2 一个让 Dijkstra 当场翻车的反例

下面这张图在第 9 篇出现过，今天再请它出来一次，因为它是理解 Bellman-Ford 最好的入口。起点是 A，B 和 C 都是从 A 出发一步可达的顶点，边权分别是 4 和 3；另外还有一条从 C 指向 B 的边，权重是 −5：

graph LR
    A["起点 A"] -->|"4"| B["B"]
    A -->|"3"| C["C"]
    C -->|"-5"| B
    style C fill:#ffd5d5

第一轮，Dijkstra 比较未确定顶点：B 的 dist 是 4，C 的 dist 是 3，于是它选中 C，宣布 C 定案。随后松弛 C 的出边，发现 3 + (−5) = −2 < 4，于是把 dist[B] 更新成 −2。看起来一切顺利？问题出在下一轮：如果 Dijkstra 的经典实现里 B 还没有定案，那么它会继续选中 B（−2 是全场最小）并给出正确答案；但请看——如果边的方向换一下，或者图中还有其他顶点使得 B 先于 C 被定案，事情就完全不一样了。更典型的情形是：B 的 dist 初始为 4，而 C 的 dist 是 3，第一轮选中 C 之后，B 的 dist 变成 −2，算法还能“补上”；可如果图里还有一个 D，dist 是 2，第一轮选中的就是 D，第二轮才轮到 C，此时 B 的 −2 依然会被发现。真正危险的是：一旦 B 在 C 松弛它之前就被定案（比如 B 的 dist 初始值比 C 小），那么 −2 这个正确答案将永远无法写入 dist[B]。

为了让灾难更直观，我们把反例改一改：A 到 B 的边权是 4，A 到 C 的边权是 3，C 到 B 的边权是 −5，同时 A 到 B 还有另一条“慢速路径”经过一个中间顶点 D，使得 D 的 dist 是 2。第一轮 Dijkstra 选 C？不对，D 的 dist 是 2，比 C 的 3 小，第一轮选中 D；第二轮选中 C，松弛出 B 的 −2；第三轮选中 B。看起来 Dijkstra 又侥幸对了。那什么时候会真正出错？当负权边让“已定案顶点”被后续路径刷新时：例如 A 到 B 直达 4，A 到 C 直达 2，C 到 B 是 −5，第一轮选中 C（2），松弛 B 得到 −3；此时 B 尚未定案，−3 仍然会被采用，算法又对了。真正致命的反例需要“先定案、后更短”的次序：A 到 B 直达 1，A 到 C 直达 3，C 到 B 是 −5。第一轮，B 的 dist 是 1，C 的 dist 是 3，于是 B 被选中并定案；第二轮选中 C，松弛 C→B 得到 3 + (−5) = −2，但 B 已经定案，−2 被丢弃。正确的最短路径明明是 A → C → B，总代价 −2，Dijkstra 却输出 1。

graph LR
    A["起点 A"] -->|"1"| B["B（先被定案）"]
    A -->|"3"| C["C"]
    C -->|"-5"| B
    B -.->|"−2 被丢弃"| X["✗"]
    style B fill:#ffaaaa

这就是第 9 篇反复警告的场景：负权边可以让“先定案的顶点”事后被一条绕远路打败。Dijkstra 的已确定集合一旦盖上章，就再也没有回头的机会；而负权边恰好破坏了“不会回头”的理论基础。

1.3 贪心证明断在了哪一行

让我们把第 9 篇的证明再拆细一点，找出负权究竟击穿了哪一行。设 S 是已确定集合，T 是未确定集合，算法选中 u ∈ T 且 u 是 T 中 dist 最小者。假设存在从起点 s 到 u 的真实最短路径 P 比 dist[u] 还短。由于 s ∈ S 而 u ∈ T，P 上必然存在一条跨过分界线的边 (x, y)：x ∈ S，y ∈ T，且从 y 到 u 的部分全部位于 T 中。于是 P 的总代价可以拆成三段：s 到 x 的代价、边 (x, y) 的权重 w(x, y)、以及 y 到 u 的后续代价。

第 9 篇的推理是：P 的总代价 ≥ dist[x] + w(x, y) ≥ dist[y] ≥ dist[u]，与“P 比 dist[u] 短”矛盾。这里一共用了三个不等号：第一个来自“s 到 x 的代价 ≥ dist[x]”（x 已定案，dist[x] 就是最短）；第二个来自“松弛保证了 dist[y] ≤ dist[x] + w(x, y)”；第三个来自“u 是 T 中 dist 最小者”。你看出问题了吗？第二个不等号与第三个不等号都安然无恙，真正出问题的是被我跳过的那个隐藏假设：y 到 u 的后续代价 ≥ 0。原文里我写的是“P 的总代价 ≥ dist[x] + w(x, y)”，这一步默认了后续部分非负；一旦 y 到 u 之间存在负权边，后续部分可能“倒贴钱”，把整条路径的总代价拉低，P 就可以比 dist[y] 甚至 dist[u] 更短。于是矛盾消失，贪心不再安全。

用一个生活比喻：Dijkstra 像一位只肯往前走、绝不回头的旅行者，他相信“路只会越走越远”。负权边相当于路上出现了“倒贴车费”的班车——先坐贵车绕到远处，再坐倒贴班车回来，总花费反而比直行便宜。旅行者若已经走到终点并盖章，就永远错过这个更优方案了。所以结论要记牢：只要存在负权边，哪怕没有负环，Dijkstra 也不保证正确。

1.4 三种世界：非负、负权无负环、有负环

在正式介绍 Bellman-Ford 之前，先把“带权最短路问题”的版图理清楚。按边权的性质，图可以分成三种世界：

第一，所有边权非负：这是 Dijkstra 的主场，BFS 是边权全为 1 时的特例。

第二，存在负权边，但不存在负环：负权边允许，只是别让它凑成一个总权重为负的环。这是 Bellman-Ford 的主场，也是本篇的核心场景。

第三，存在可达的负环：总权重为负的环一旦出现，“最短路径”本身就没有意义了，因为你可以绕着负环无限转圈，把总代价压到负无穷。此时算法能做的不是给出距离，而是检测并报告负环。

注意“负权边”和“负环”是两个不同的概念：一条边是负数，不代表一定存在负环；反过来，存在负环则必然有负权边。很多初学者一看到负数就慌了，其实只要负权边没有连成负环，最短路问题依然有良好定义，Bellman-Ford 可以放心求解。这一点我们会在第 6 章详细展开。

1.5 Bellman-Ford 的应对思路

面对负权，Bellman-Ford 的应对思路朴素到令人感动：既然“按顺序贪心”不可靠，那就不贪心——把所有边不分先后地全部松弛一遍，然后重复做 V−1 遍。第一遍松弛，所有“用 1 条边就能到达”的顶点的距离至少会被刷新一次；第二遍，所有“用 2 条边就能到达”的顶点也会被覆盖；以此类推，到第 V−1 遍时，任何不含负环的最短路径（最多 V−1 条边）都被充分松弛过了。这个“笨办法”的正确性不依赖边权正负，也不依赖松弛顺序，所以它天生不怕负权。代价是慢：O(V·E)，比 Dijkstra 慢一个量级，但这正是“不怕负权”的合理价格。接下来两章，我们把“为什么 V−1 轮就够”和“松弛到底在做什么”彻底讲透。

1.6 三个常见误区：负权不是“改改就行”

在进入正题前，顺手拆掉三个围绕负权的经典误区，免得你在题海里踩坑。误区一：“负权边少见，把负数取绝对值不就行了？”不行。最短路问题里，边权是语义的一部分：权重是成本，负权重代表“收益”。取绝对值会把“这条路倒贴钱”变成“这条路收钱”，问题的答案随之改变，算出来的根本不是你要求的东西。误区二：“给所有边权同时加一个大常数，把负数变成正数，再用 Dijkstra 不行吗？”也不行。同时平移所有权重，会改变不同长度路径之间的相对差距：一条 3 条边的路径每条 +100，总代价多 300；一条 5 条边的路径总代价多 500，原本更优的 5 边路径可能被 3 边路径反超。最短路径对“整体平移”不敏感，但“每条边加常数”不是平移，是加权的路径长度惩罚。误区三：“有负权边的图，最短路问题就没法做了。”不对，只要没有负环，问题依然有良好定义，Bellman-Ford 就是专门为它准备的；有负环才叫无解，而且“无解”的判定本身也是一道标准题。

这三个误区有一个共同的根源：把边权当成无关紧要的数字，而不是问题模型的一部分。负权不是 bug，是信息；算法要做的不是把负数“修”成正数，而是设计一种不怕负数的计算方式。Dijkstra 做不到，Bellman-Ford 可以——这就是本篇存在的意义。

2 松弛操作：算法唯一的发动机

2.1 松弛的定义

在第 9 篇我们见过松弛，但今天它要升级成绝对主角，所以值得重新、完整地定义一次。假设当前我们掌握了一条到顶点 u 的路径，总代价是 dist[u]；从 u 出发有一条边通向 v，权重是 w(u, v)。那么“先走这条已知路径到 u，再沿这条边走到 v”的总代价就是 dist[u] + w(u, v)。如果这个值比目前已知的 dist[v] 更小，我们就更新：

if (dist[u] + w(u, v) < dist[v]) {
    dist[v] = dist[u] + w(u, v);
}

这个“检查并更新”的动作就叫松弛（relaxation）。注意几个细节：第一，松弛只发生在“能找到更短路径”的时候，否则什么都不做；第二，被更新的是“当前已知的最短距离估计值”，不是“最终答案”，dist[v] 以后还可能被再次刷新；第三，松弛是几乎所有最短路算法的唯一引擎——BFS、Dijkstra、Bellman-Ford、SPFA、Floyd 的区别，仅仅是“以什么顺序、松弛多少次”。

2.2 为什么叫“松弛”

“松弛”这个名字来自一个非常形象的物理比喻：把 dist[v] 想象成一根绷在起点和 v 之间的橡皮筋，它现在的长度是 10，被拉得紧紧的；突然你发现还有一条路，总代价只要 7，于是橡皮筋“放松”到 7，变得更短、更松弛。只要还有更短的路被发现，橡皮筋就继续放松；当所有可能的更短路都被找过一遍、再也放松不动时，它就停在真正的最短长度上。

flowchart LR
    subgraph B["松弛前：dist[v] = 10，绷得很紧"]
        U1["u（dist=3）"] -->|"w=4"| V1["v（dist=10）"]
    end
    subgraph A["松弛后：dist[v] = 7，放松下来"]
        U2["u（dist=3）"] -->|"w=4"| V2["v（dist=7）"]
    end
    B --> A

上图是松弛的微观快照：已知 dist[u] = 3，边 (u, v) 的权重是 4，那么经过 u 到 v 的候选代价是 7，小于当前 dist[v] = 10，于是 v 的距离被更新为 7。整个过程没有任何复杂的决策，只有一个比较和一次赋值——但正是这个简单的动作，被反复执行足够多次之后，就能“磨”出全局最短路径。

2.3 dist 永远对应一条真实路径

松弛有一个极其重要、却常常被忽略的性质：dist[v] 在任何时刻都对应着一条从起点 s 到 v 的真实路径的总代价，它是一个“上界”。为什么？因为 dist[v] 的每一次变化都来源于某条真实存在的边 (u, v)：新值等于“dist[u]（对应一条真实路径）+ w(u, v)（一条真实边）”，拼接起来就是一条新的真实路径。初始时 dist[s] = 0 对应空路径，其余顶点是无穷大，代表“尚未发现任何路径”，也不违反这个性质。所以松弛操作绝不会“发明”一条不存在的路径，它只是在所有真实路径里不断挑选更优者。

这个性质带来两个推论。第一，如果算法结束时 dist[v] 仍然是无穷大，说明 s 到 v 根本不可达，而不是“距离真的无穷大”。第二，我们不需要担心松弛会把 dist 改成一个“看起来更小但走不通”的值——每个 dist 值都脚踏实地，背后都有一条拿得出手的路径。这也是为什么“最短路径还原”永远可行：只要在每次成功松弛时记下前驱 prev[v] = u，最终就能从任何顶点沿着前驱链一路回溯到起点。

2.4 同一条边可以被松弛很多次

初学者最容易困惑的一点：一条边 (u, v) 为什么要被检查很多遍？答案很简单：dist[u] 本身会变。第一次检查 (u, v) 时，dist[u] 可能是 8，候选值 8 + w 不够小，松弛失败；几个回合后，另一条路径把 dist[u] 刷新成 3，再次检查 (u, v) 时，候选值 3 + w 可能就赢了。换句话说，松弛 (u, v) 的收益取决于“检查的那一刻 dist[u] 有多好”，而 dist[u] 会随着算法推进不断变好，所以同一条边必须被反复“骚扰”，直到 dist[u] 稳定下来为止。

BFS 里每条边只被处理一次，是因为无权图里“第一次到达就是最短”，不需要回头；Dijkstra 里每个顶点只定案一次，是因为非负权保证了“定案后不会再变”。Bellman-Ford 主动放弃这些保证，换取对负权的兼容，因此它的每一轮都要把全部 E 条边重新松弛一遍——这正是 O(V·E) 复杂度的来源。你可以把每一轮想象成“全图广播”：所有顶点把当前已知的最佳距离通过各自的出边传播给邻居，一轮传播一跳。

2.5 松弛就是“信息沿边传播”

把“一轮松弛 = 一次全图广播”这个直觉再夯实一点。假设有一条最短路径 s → a → b → c → t，共 4 条边。第 1 轮松弛后，距离信息最多传播 1 条边：a 的 dist 会被 s 刷新，但 b 要等到第 2 轮才能通过 a 获得正确值，c 等到第 3 轮，t 等到第 4 轮。为什么“最多”1 条边？因为每一轮里所有边都会被检查，而一次成功的松弛最多把信息向前推进一条边；如果第 1 轮里 (s, a) 恰好排在被检查的边后面，而 (a, b) 排在最前面，那么 a 在检查 (a, b) 时还没被刷新，b 就得等到下一轮——这就是“最多”的含义。好消息是，无论顺序多差，每一轮至少能把信息向前推进一条边，所以 k 轮之后，所有“用不超过 k 条边就能到达”的顶点的距离一定已经被正确刷新。下一章我们要把这个直觉变成严格的引理。

flowchart LR
    S["s"] -->|"第 1 轮后到达"| A["a"]
    A -->|"第 2 轮后到达"| B["b"]
    B -->|"第 3 轮后到达"| C["c"]
    C -->|"第 4 轮后到达"| T["t"]

这张小图就是“一轮传播一跳”的示意图：距离信息像接力棒一样，从起点出发，沿着最短路径的边逐轮传递，第 k 轮结束时刚好传到第 k 个顶点。如果一条最短路径有 4 条边，那么在第 4 轮结束时，它的终点 t 一定已经拿到正确距离。而任何无负环图的最短路径都不会超过 V−1 条边——这就是 Bellman-Ford 只刷 V−1 轮的理论依据。

2.6 松弛的三条代数性质

把松弛操作的性质总结成三条，以后遇到任何“类松弛”算法都能快速验证。第一条，单调不增：dist[v] 只会在成功松弛时变小，永远不会变大，因此每个顶点的 dist 值序列是单调下降的。第二条，上界性：任何时刻 dist[v] 都对应一条真实路径的总代价（2.3 节），所以它不可能低于真正的最短距离——算法只能从“∞ 或较大的估计”一路向下逼近，绝不会“低估过头”再补回来。第三条，收敛性：在无负环的图里，每个顶点最多被成功松弛有限次。为什么？每次成功松弛都意味着发现一条“当前最短”的新路径，而无负环时最短路径可以写成简单路径，数量有限；更进一步，Bellman-Ford 的 V−1 轮理论保证，任何顶点的有效更新次数不超过 V−1。

这三条性质合起来，解释了 Bellman-Ford 为什么“一定会停、停得对”：单调不增保证过程不会震荡，上界性保证不会低于答案，V−1 轮的收敛性保证有限的松弛次数足以让每个 dist 触达答案。反过来，如果某个顶点被松弛了 V 次以上，唯一可能违反“收敛性”的就是图中出现了负环——这正是负环检测判据的代数版本。

2.7 松弛的顺序：Dijkstra 与 Bellman-Ford 的分水岭

既然松弛是唯一的发动机，为什么 Dijkstra 和 Bellman-Ford 的表现如此不同？答案全在松弛的顺序里。Dijkstra 的松弛是“按需定点”的：每一轮选出 dist 最小的未确定顶点 u，立刻松弛 u 的全部出边；因为非负权保证了“先定案者不可能再被反超”，每个顶点的出边只需被松弛一次，总工作量就是 O(V) 次定点 + O(E) 次松弛。Bellman-Ford 的松弛是“按轮全量”的：不挑顶点、不排序，每一轮把全部 E 条边都松弛一遍，一共 V−1 轮，总工作量 O(V·E)。两者的发动机相同，区别只是“一次扫哪些边、扫几遍”。

这个分水岭还解释了另一个现象：为什么 Dijkstra 在负权图上会错，而 Bellman-Ford 不会。Dijkstra 的“只松弛一次”建立在“定案后不再更新”的假设上；负权边能制造“定案后被反超”，让这个假设破产。Bellman-Ford 从一开始就不做“定案”承诺，它允许任何顶点的 dist 在任意轮次被反复刷新，直到 V−1 轮后自然稳定——不依赖顺序，所以也不怕负权。你可以把 Bellman-Ford 理解成“Dijkstra 放弃排序后得到的稳健版本”：放弃了优雅，换来了全面。理解了这个分水岭，两个算法就不再是两个孤立模板，而是同一台发动机的两种调速方式。

3 核心思想：最短路径最多 V−1 条边

3.1 先问一个基本问题：最短路径能有多长

“多长”在这里不是指权重，而是指经过几条边。直觉告诉我们，一条“合理”的最短路径不应该绕圈子：如果一条路径里出现了重复顶点，比如 s → a → b → a → t，那么把中间那段 a → b → a 的环删掉，就得到一条更短的路径 s → a → t。删掉环之后总权重会不会反而变大？这取决于环的符号：如果环的总权重是正数，删掉它总权重必然变小；如果环的总权重是 0，删掉它总权重不变；如果环的总权重是负数，删掉它总权重会变大——但等等，负环不是“不该删”，而是根本不允许出现。在第 6 章我们会看到，负环会让最短路失去定义。所以在“无负环”的假设下，任何最短路径都可以被改写成一条简单路径：不重复经过任何顶点。

一条简单路径最多包含 V 个顶点，因此最多有 V−1 条边。这个结论平凡却威力巨大：它告诉我们，只要把“边数不超过 V−1 的所有路径”都考虑一遍，就一定能找到真正的最短路径。Bellman-Ford 的策略因此变得非常具体：不用像 Dijkstra 那样小心翼翼地排序，只需要保证“经过 k 条边的路径”在第 k 轮被充分处理，k 从 0 数到 V−1 即可。

3.2 路径展开：为什么环可以去掉

我们用一张图把“为什么最短路径不含环”看个清楚。假设从 s 到 t 有一条路径 s → a → b → a → t，它经过顶点 a 两次，中间夹着环 a → b → a：

graph LR
    S["s"] --> A1["a"]
    A1 --> B["b"]
    B --> A2["a（第二次出现）"]
    A2 --> T["t"]
    A1 -.->|"中间这段是环"| B

如果环 a → b → a 的权重是正数，删掉它，路径变成 s → a → t，总权重严格变小，原路径不可能是最短的；如果环的权重是 0，删掉它总权重不变，我们照样可以得到一条更短的（边数更少的）最短路径。所以总存在一条最短路径不经过任何环——除非图中存在负环，而负环情况下的“最短路径”概念本身已经失效。这个论证不依赖于边权是否为正，只依赖于“无负环”这一个前提，因此对负权边同样成立。

3.3 关键引理：第 k 轮之后，k 条边以内的路径全部被覆盖

现在给出 Bellman-Ford 正确性的核心引理：

引理：设算法已经完整执行了 k 轮“对所有边松弛一遍”。那么对任意顶点 v，如果存在一条从 s 到 v、边数不超过 k 的路径，则 dist[v] 一定不大于这条路径的总权重。

换句话说，第 k 轮结束时，所有“用不超过 k 条边就能到达”的顶点，其 dist 都已经收敛到这些短路径中的最小值。这个引理可以用数学归纳法证明：

基础情形 k = 0：dist[s] = 0，s 到 s 的 0 边路径权重是 0，其他顶点没有 0 边路径，引理成立。

归纳步骤：假设第 k 轮结束时引理成立，考虑第 k+1 轮。设 P 是从 s 到 v 的任意一条边数不超过 k+1 的路径。若 P 的边数不超过 k，归纳假设已经保证 dist[v] ≤ w(P)；若 P 恰好有 k+1 条边，设 P 的最后一条边是 (u, v)，前缀 P′ 是 s 到 u 的路径，边数为 k。由归纳假设，第 k 轮结束时 dist[u] ≤ w(P′)。第 k+1 轮会松弛边 (u, v)，检查 dist[u] + w(u, v) 是否小于 dist[v]；由于 dist[u] ≤ w(P′)，候选值 ≤ w(P′) + w(u, v) = w(P)，所以这一轮结束后必有 dist[v] ≤ w(P)。引理得证。

这个证明最妙的地方在于：它完全没用到松弛顺序。不管每条边在第 k+1 轮内部谁先谁后，边 (u, v) 一定会在某一次被检查，而检查时 dist[u] 至少已经是第 k 轮结束时的值（一轮内部只会让它更小，不会更大）。所以 Bellman-Ford 对“边集顺序”零要求——这正是它朴素而稳健的原因。

3.4 为什么是 V−1 轮，而不是 V 轮或 V+1 轮

把 3.1 和 3.3 接起来：无负环时，存在一条最短路径是简单路径，边数至多 V−1；第 V−1 轮结束时，引理保证这条路径的终点已经拿到不超过其总权重的 dist；又因为 dist 永远对应一条真实路径（上界），两者一夹，dist 就恰好等于最短路径长度。V−1 轮之后，所有可达顶点的 dist 都不可能再变。那第 V 轮拿来干什么？专门做负环检测：如果第 V 轮还能找到一条边让 dist 变小，说明“边数不超过 V−1 的路径”已经全部算完，却仍然存在更短的路径，唯一的解释就是这条更短路径里含有负环。第 6 章会完整展开这个推理。

至于“为什么不刷 V 轮就完事”：在第 V 轮之前，正常图早就收敛了；多刷一轮不是为了求答案，而是为了给“负环”做一个决定性测试。这是 Bellman-Ford 最漂亮的附加功能：同样的松弛循环，前面 V−1 轮用来求解，最后一轮用来判案。

3.5 一轮传播一跳的全局视图

把“k 轮之后覆盖 k 条边”的直觉画成一张递进图，一眼就能记住：

flowchart TD
    R0["第 0 轮后：只有起点 s 有值（0 条边）"] --> R1["第 1 轮后：所有 1 条边可达的顶点有值"]
    R1 --> R2["第 2 轮后：所有 2 条边可达的顶点有值"]
    R2 --> RK["…… 第 k 轮后：所有 k 条边可达的顶点有值"]
    RK --> RN["第 V-1 轮后：所有最短路收敛，因为最长简单路径只有 V-1 条边"]

请特别注意“所有”二字的分量：每一轮都是全图扫描，所以不是只处理某一条特定路径，而是同时推进图中所有路径的传播。第 k 轮结束后，任何“边数 ≤ k”的路径都被覆盖——这就是引理所说的“全部覆盖”。相比之下，Dijkstra 像一位精心排队的服务员，每次只服务一个最紧急的顾客；Bellman-Ford 像一位不看名单的广播员，每次把消息发给所有人，发 V−1 遍之后，消息自然到达每一个能到达的角落。广播员笨，但广播员不会漏人。

3.6 最短路径树视角：为什么“V−1 轮”像在长一棵树

还有一个更直观的视角：把从起点 s 出发的所有最短路径合在一起看，它们天然形成一棵最短路径树——每个顶点（除 s 外）选择一条“让我距离最短”的前驱边，前驱指向更靠近 s 的顶点，最终所有前驱链都收束到 s。树有 V 个顶点，因此恰好 V−1 条边，最深的一条根到叶路径的边数不超过 V−1。Bellman-Ford 的每一轮全图松弛，本质上都在“生长”这棵树：第 k 轮结束时，树中所有深度不超过 k 的顶点都已经拿到正确距离；下一轮，深度 k+1 的顶点通过一条新的前驱边被点亮。

这个视角把“V−1 轮”从一句死记硬背的话变成了几何直觉：树只有 V−1 层深度，广播消息当然最多需要 V−1 跳。它也解释了为什么提前终止常常很有效：如果图的直径（最短路径树的最大深度）远小于 V−1，算法早就把整棵树点亮了，后面的轮次只是确认“没东西可更新”。而负环的存在，会让这棵树永远“长不完”——总有一条边能造出更浅的深度，于是第 V 轮检测就是给这棵企图无限生长的树踩刹车。

3.7 边界情形：零环、自环与重边

把“环”的三种符号彻底分清楚，很多边界题就迎刃而解。正环：总权重大于 0，最短路径绝不可能包含它，删掉一定更短，Bellman-Ford 会自动忽略。零环：总权重等于 0，最短路径包含它不改变答案，但总会存在一条不含它的等价最短路径，所以“简单路径”假设依然成立。负环：总权重小于 0，破坏最短路定义，必须检测。零环是三者里最容易让人疑惑的：图中明明有环，为什么 Bellman-Ford 还正确？因为零环既不提供“更短”的路径，也不会让 dist 无限下降，它只是让“最短路径”在数量上变多，不影响距离值本身。

自环和重边同理：负自环就是最简单的负环（一个顶点构成的环），正自环和零自环不影响答案；重边之间相互独立竞争，松弛条件自然留下最优者。练习时建议刻意构造这三种边界各跑一遍 Bellman-Ford，亲眼确认输出符合预期——这比背十遍结论都牢。

4 算法步骤与手算：一张负权图的完整走查

4.1 算法步骤

把前面所有讨论汇成 Bellman-Ford 的标准流程，一共四步：

1. 初始化：dist[s] = 0，其余顶点 dist = ∞；如果要做路径还原，再准备 prev 数组，全部置为 −1。
2. 主循环：重复 V−1 次，每一次遍历全部 E 条边，对每条边 (u, v, w) 尝试松弛：若 dist[u] ≠ ∞ 且 dist[u] + w < dist[v]，则更新 dist[v]，并记录 prev[v] = u。
3. 负环检测：再遍历一次全部边，若还有边能松弛，则报告“存在从 s 可达的负环”，算法返回失败；否则返回 dist 数组作为答案。
4. （可选优化）提前终止：如果某一轮遍历中没有任何一条边被成功松弛，说明 dist 已经收敛，可以提前跳出主循环。

步骤 2 是整个算法的主体，步骤 3 是点睛之笔，步骤 4 只是工程上的加速，不影响正确性。下面用一张带负权的小图，把步骤 2 的每一轮都摊开来看。

4.2 走查用图：一条需要 4 轮才能传播到位的路径

我们选一张有 5 个顶点（V = 5，所以主循环刷 4 轮）、6 条边的有向图。顶点是 S、A、B、C、T，边集如下（注意边的顺序是故意打乱的，用来展示“顺序无所谓”）：

graph LR
    S["S"] -->|"4"| A["A"]
    S -->|"8"| B["B"]
    A -->|"-3"| B
    B -->|"2"| C["C"]
    B -->|"10"| T["T"]
    C -->|"-1"| T

真实的最短距离是：S 到 A 为 4（直达）；S 到 B 为 1（走 S → A → B，4 + (−3) = 1，比直达的 8 便宜）；S 到 C 为 3（走 S → A → B → C，1 + 2 = 3）；S 到 T 为 2（走 S → A → B → C → T，3 + (−1) = 2）。特别留意 S 到 T 的最短路径一共经过 4 条边，因此在边序不利时，它要等到第 4 轮才会收敛——这正好检验“V−1 轮足够”的理论。我们把边集固定成下面这个顺序，模拟最糟糕的输入：

1. (B, T, 10)
2. (S, B, 8)
3. (C, T, −1)
4. (B, C, 2)
5. (A, B, −3)
6. (S, A, 4)

为什么要这么排？因为每条“关键路径”的边都恰好排在“前一条边”的后面，例如 (A, B, −3) 排在 (S, A, 4) 前面，所以第 1 轮里 A 还没被刷新，(A, B) 就白检查了一次；类似地 (B, C, 2) 排在 (A, B) 前面、(C, T, −1) 排在 (B, C) 前面。这样一来，正确的距离必须一轮一轮“挤牙膏”式地传播，过程最有教学价值。

4.3 逐轮走查：dist 表的变化

初始化：dist = [S: 0, A: ∞, B: ∞, C: ∞, T: ∞]。

第 1 轮：按顺序松弛全部 6 条边。

• (B, T, 10)：dist[B] = ∞，跳过。
• (S, B, 8)：dist[B] = 8。
• (C, T, −1)：dist[C] = ∞，跳过。
• (B, C, 2)：dist[C] = 8 + 2 = 10。
• (A, B, −3)：dist[A] = ∞，跳过。
• (S, A, 4)：dist[A] = 4。

第 1 轮结束时：dist = [S: 0, A: 4, B: 8, C: 10, T: ∞]。这一轮只覆盖了“1 条边”的路径：A 和 B 直达成功，C 走了 2 条边（S→B→C）纯属侥幸——因为 (S, B) 恰好排在 (B, C) 前面。

第 2 轮：

• (B, T, 10)：dist[T] = 8 + 10 = 18。
• (S, B, 8)：8 < 8 不成立，跳过。
• (C, T, −1)：dist[T] = min(18, 10 − 1) = 9。
• (B, C, 2)：8 + 2 = 10 不小于 10，跳过。
• (A, B, −3)：dist[B] = min(8, 4 − 3) = 1。
• (S, A, 4)：跳过。

第 2 轮结束时：dist = [S: 0, A: 4, B: 1, C: 10, T: 9]。B 被 2 条边的路径 S→A→B 刷新为 1；T 拿到了 9（3 条边 S→B→C→T），但还不是最优。

第 3 轮：

• (B, T, 10)：dist[T] = min(9, 1 + 10) = 9。
• (S, B, 8)：跳过。
• (C, T, −1)：dist[T] = min(9, 10 − 1) = 9。
• (B, C, 2)：dist[C] = min(10, 1 + 2) = 3。
• (A, B, −3)：跳过。
• (S, A, 4)：跳过。

第 3 轮结束时：dist = [S: 0, A: 4, B: 1, C: 3, T: 9]。C 被 3 条边的路径 S→A→B→C 刷新为 3；T 的 9 还没动，因为最优的 4 条边路径还差最后一棒。

第 4 轮：

• (B, T, 10)：dist[T] = min(9, 1 + 10) = 9。
• (S, B, 8)：跳过。
• (C, T, −1)：dist[T] = min(9, 3 − 1) = 2。
• (B, C, 2)：跳过。
• (A, B, −3)：跳过。
• (S, A, 4)：跳过。

第 4 轮结束时：dist = [S: 0, A: 4, B: 1, C: 3, T: 2]。T 终于在最后一轮拿到最优值 2，整张表收敛。

把四轮结果并成一张表，变化一目了然：

4.4 从走查里读出的三件事

第一，收敛速度取决于最长最短路径的边数。T 的最优路径有 4 条边，于是它精确地在第 4 轮收敛；如果这张图有 100 个顶点、最优路径有 99 条边，那就得刷满 99 轮。这就是“V−1 轮”这个数字的来源。

第二，同一轮内部，边的先后顺序只影响“几轮能收敛”，不影响“最终答案”。我们的边序已经刻意刁难，4 轮后照样收敛；哪怕顺序再乱，第 V−1 轮结束时的 dist 也一定正确。原因就是 3.3 的引理：每一轮无论如何都要把所有边检查一遍。

第三，提前终止很有用。观察这张表，第 4 轮之后如果再做第 5 轮，所有边都无法松弛。工程实现可以加一个 updated 标志：某轮没有任何更新就直接 break。本例其实在第 4 轮就全部收敛，多跑的轮次全是浪费。

4.5 用路径传播图再复盘一遍

把四条关键路径按“第几轮被传播到”画成一张时间线图，你会更直观地看到“一轮一跳”：

flowchart TD
    R1["第 1 轮：S→A=4，S→B=8"] --> R2["第 2 轮：S→A→B=1"]
    R2 --> R3["第 3 轮：S→A→B→C=3"]
    R3 --> R4["第 4 轮：S→A→B→C→T=2"]

注意第 2 轮里 T 还出现过 9 这个中间值（走 S→B→C→T），它在第 4 轮才被 2 取代——这再次说明 dist 只是“当前已知上界”，会随着信息传播不断被更好的路径刷新。手算到这里，Bellman-Ford 的“笨但可靠”已经展露无遗。下一章，我们把这份手算翻译成可以运行的代码。

4.6 如果边的顺序换一换，会发生什么

我们刚才故意把边序排成“最坏情况”，让正确距离像挤牙膏一样一轮传一跳。现在反过来想：如果边集恰好按“路径方向”排列，比如 (S, A, 4)、(A, B, −3)、(B, C, 2)、(C, T, −1)、(S, B, 8)、(B, T, 10)，那么第 1 轮就会发生连锁反应：S→A 先把 A 刷新成 4，紧接着 A→B 把 B 刷新成 1，B→C 把 C 刷新成 3，C→T 把 T 刷新成 2——一条 4 条边的路径在同一轮内部就全部传播完毕，第 1 轮结束时整张表已经收敛。同样的图、同样的答案，只是因为输入顺序不同，收敛轮数从 4 轮变成 1 轮。

这个对比说明了三件事。第一，Bellman-Ford 的正确性完全不依赖边序：顺序再好、再坏，V−1 轮之后答案都一样。第二，收敛快慢依赖边序：好的顺序一轮到位，坏的顺序要一轮传一跳，所以“提前终止”优化在数据友好时能省下大量轮次。第三，也是最容易被忽略的：存在总能让某条路径“一整轮都传不动”的边序——把每条边的位置都排在前驱边之前即可。正是这种最坏情况，决定了理论复杂度必须按 V−1 轮来写，而不是按“平均几轮收敛”来写。理解了这一点，你就不会再问“为什么不能刷几轮就停”了：可以提前停，但保证一定正确的最坏情形，就是刷满 V−1 轮。

4.7 手算与代码的逐行对照

如果你觉得自己“手算会、写码懵”，下面这张对照表能帮你把第 4 章的手算过程映射到代码的每一行。初始化对应 dist[s] = 0 与 new Array(n).fill(Infinity)；每一轮的“按顺序扫完全部边”对应内层 for (const { u, v, w } of edges)；“dist[B] = 8”这类更新对应 dist[v] = dist[u] + w；“跳过”对应条件判断 dist[u] !== Infinity && dist[u] + w < dist[v] 不成立；“这一轮有没有白跑”对应 updated 标志；“第 4 轮之后再做第 5 轮会发现没有更新”对应提前终止 if (!updated) break；“最后一轮扫描”对应检测循环。换句话说，你手算时写的每一个数字，都是代码里某次成功松弛的产物；你手算时省略的每一条无效边，都是代码里一次失败的 if 判断。

这张表背下来，手算能力和代码能力就“接通”了：以后再遇到新图，先在纸上走两轮，再用代码验证，两者对不上就说明哪边理解有偏差——对不上本身就是最好的学习信号。

5 代码实现：JS/TS 边集版，逐行解释

5.1 为什么用“边集”而不是邻接表

Bellman-Ford 每一轮都要遍历全部边，而且对遍历顺序没有要求，所以最简单的存储方式就是“边集”：把所有边塞进一个数组，每条边记成 { u, v, w }。邻接表当然也能用——先把每条边展平，或者每一轮双重循环顶点与出边——但边集让“全图扫一遍”这件事变得一目了然。第 3 篇我们学过三种存储方式：邻接矩阵适合稠密图，邻接表适合稀疏图，边集则是最适合“按边批处理”的算法。这里顺带说一句：如果题目给你的输入就是若干条 (u, v, w)，那么连建图都省了，直接把这个三元组数组丢给 Bellman-Ford 即可。

5.2 完整代码

下面是一个 TypeScript 实现。函数接收顶点数 n、边集 edges、起点 s；返回距离数组 dist；如果检测到从 s 可达的负环，返回 null：

type Edge = { u: number; v: number; w: number };

function bellmanFord(n: number, edges: Edge[], s: number): number[] | null {
  const dist = new Array<number>(n).fill(Infinity);
  dist[s] = 0;

  // 主循环：松弛全部边 V-1 轮
  for (let round = 0; round < n - 1; round++) {
    let updated = false;
    for (const { u, v, w } of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        updated = true;
      }
    }
    if (!updated) break; // 提前终止：本轮没有任何更新
  }

  // 第 V 轮：负环检测
  for (const { u, v, w } of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      return null; // 还能松弛 => 存在从 s 可达的负环
    }
  }

  return dist;
}

加上路径还原的完整版也很短：准备 prev 数组，每次成功松弛时记录 prev[v] = u；主循环与检测循环里都要同步更新 prev（虽然检测循环里的更新只是为了“标记有负环”，并不会真的使用）。还原时从目标顶点沿 prev 一路回溯到起点，再反转数组即可。为了保持本文聚焦，下面先逐行解释上面这个基础版。

5.3 逐行解释

第一行到第三行：定义边的类型并声明函数。n 是顶点数，顶点编号 0 到 n−1；edges 是全部边的数组；s 是起点。返回值用 number[] | null 明确表达“可能无解”的语义，比返回一个全是负数或者特殊标记的数组要清晰得多。

第四到第五行：初始化 dist。new Array<number>(n).fill(Infinity) 把每个顶点都设为无穷大，表示“尚未找到路径”，然后把起点的距离设为 0。JavaScript 的 Infinity 在这里有两个好处：一是不会像整数溢出那样变成负数，二是 Infinity + 任何有限数 依然是 Infinity，天然安全。

第七行到第十六行：主循环。外层 for (let round = 0; round < n - 1; round++) 精确执行 V−1 轮；内层 for (const { u, v, w } of edges) 每一轮把全部边扫一遍。松弛条件 dist[u] !== Infinity && dist[u] + w < dist[v] 里那个 !== Infinity 检查非常关键：如果 dist[u] 还是无穷大，说明 s 还没找到任何路径到 u，Infinity + w 虽然也是 Infinity，但用“还没打通”的顶点去刷新别人在语义上不成立，显式检查也让代码意图更清楚。

第九行的 updated 标志实现 4.4 节说的提前终止：只要某一轮没有任何边成功松弛，说明 dist 已经收敛，再刷也是白刷。注意提前终止不会破坏负环检测——如果存在负环，每一轮必然都有更新，循环会一直跑满 V−1 轮，绝不会提前退出。

第十八行到第二十三行：负环检测。主循环结束后再扫一遍全部边，如果还能找到 dist[u] + w < dist[v]，就说明存在从 s 可达的负环，返回 null。为什么这个判断是可靠的？因为第 V−1 轮结束时，所有“边数不超过 V−1 的路径”都已经充分处理；此时还能松弛，只可能是存在一条边数更多、且总权重更小的路径，而这种路径必然包含负环。这个推理是第 6 章的主角，这里先记住代码形态。

5.4 复杂度分析

时间上，主循环最多执行 V−1 轮，每轮遍历 E 条边，所以松弛部分的时间是 O(V·E)；负环检测只多扫一遍边，是 O(E)。总时间复杂度 O(V·E)。空间上，我们只额外用了 dist 数组（和可选的 prev 数组），都是 O(V)；边集本身是输入，占 O(E)。注意如果边集是题目输入的一部分，通常不计入额外空间，所以算法总空间可以写 O(V)。

把这个复杂度放回实际场景感受一下：V = 1000、E = 10000 时，O(V·E) = 10⁷，普通机器毫秒级完成；V = 10⁵、E = 10⁵ 时，运算量是 10¹⁰，就会很吃力。所以 Bellman-Ford 适合顶点数和边数都在几千到几万量级的问题，或者“必须检测负环”的场景；大规模稀疏图的单源最短路还是交给 Dijkstra。工程上的经验法则是：E 在 10⁵ 以上且不需要负权处理时，别用 Bellman-Ford；需要负权或负环检测时，它就是唯一且正确的选择之一。

5.5 写代码最容易踩的三个坑

第一个坑：忘记 dist[u] !== Infinity 检查。虽然 Infinity 加任何数还是 Infinity，不会产生错误结果，但有些语言里用很大的整数当 INF（比如 10⁹），一旦 INF + w 溢出变成负数，整个算法会瞬间崩溃。用 JavaScript 的 Infinity 可以规避，但如果你在 C++ 或 Java 里写，务必用“足够大且加 w 不会溢出”的 INF，或者干脆判断 if (dist[u] == INF) continue。

第二个坑：把检测循环写进主循环里。正确做法是“先刷 V−1 轮，再单独做第 V 轮检测”。如果把检测条件放在每一轮末尾，可能会在正常收敛但尚未跑满轮数时误报负环。另外，用提前终止时尤其要小心：某轮没有更新就 break，然后立刻做检测——这时检测依然有效，因为“没更新”本身就说明负环不存在。

第三个坑：路径还原时忘记同步 prev。prev 必须和 dist 在同一时刻、同一条件（成功松弛）下更新，否则还原出来的路径与 dist 对不上。负环检测循环里如果还更新了 dist，理论上 prev 也会被污染，但因为检测到负环后函数直接返回 null，路径还原根本不会执行，所以实际影响不大——但代码风格上还是建议把“更新 dist 和 prev”封装成同一个动作。

5.6 重边与自环

重边（两条 u→v 权重不同的边）对 Bellman-Ford 毫无影响：每条边都会被独立检查，松弛条件自然会留下更小的那个。自环 (u, u, w) 也一样：如果 w ≥ 0，dist[u] + w < dist[u] 永不成立；如果 w < 0，它本身就是一个负环（自环总权重就是负的），第 V 轮检测会把它揪出来。所以不需要像某些实现那样预处理重边，直接原样丢给算法即可。

5.7 带路径还原的完整实现

很多题目不光要距离，还要整条路径。前面提过 prev 数组的思路，这里给出完整可用的代码，并且把“更新 dist 与 prev”绑在同一个动作里：

type Edge = { u: number; v: number; w: number };

function bellmanFordPath(
  n: number,
  edges: Edge[],
  s: number
): { dist: number[]; prev: number[] } | null {
  const dist = new Array<number>(n).fill(Infinity);
  const prev = new Array<number>(n).fill(-1);
  dist[s] = 0;

  for (let round = 0; round < n - 1; round++) {
    let updated = false;
    for (const { u, v, w } of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        prev[v] = u; // 与 dist 同步更新，保证路径与距离一致
        updated = true;
      }
    }
    if (!updated) break;
  }

  for (const { u, v, w } of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      return null; // 有负环，路径无意义
    }
  }

  return { dist, prev };
}

function restorePath(prev: number[], target: number): number[] | null {
  const path: number[] = [];
  for (let cur = target; cur !== -1; cur = prev[cur]) {
    path.push(cur);
    if (path.length > prev.length) return null; // 防御：异常前驱链
  }
  return path.reverse();
}

逐块看：prev 初始全部为 −1，其中起点 s 的 prev 保持 −1，表示“路径到此结束”。每次成功松弛，prev[v] = u 记录“当前最优路径上，v 的前一个顶点是 u”。还原时从目标顶点沿着 prev 一路向前走，走到 −1 说明回到起点，再把路径反转成“从起点到终点”的顺序。如果途中发现 prev 链长度超过顶点数，说明数据结构被污染（正常算法不会发生），返回 null 兜底。至于不可达判断，建议调用方额外检查 dist[target] 是否为 Infinity，而不是依赖 restorePath 内部的启发式判断——一个 -1 的 prev 既可能是“起点”，也可能是“不可达”，两者的区分必须交给调用方。

还有两个工程细节值得强调。第一，检测到负环时不要尝试还原路径：负环上任何“最短路径”都不存在，还原出来的链只会绕圈或指向荒谬的前驱，直接返回 null 让调用方处理。第二，如果题目要求“任意一条最短路径”且存在多条并列最短路径，prev 记录的是“最后一次成功松弛”的那条，具体是哪条取决于边序；大多数题目只要求任意一条，这完全够用。

5.8 一个容易被低估的优化：把边存成三个平行数组

边集用对象数组 { u, v, w } 写起来最直观，但在性能敏感的场合，对象访问有额外开销。竞赛里常见的写法是三个平行数组 const U = new Int32Array(m), V = new Int32Array(m), W = new Int32Array(m)，主循环直接按下标遍历。这样既减少内存分配，又让 CPU 缓存更友好——三块连续内存的遍历速度远高于散落的对象。这不是算法层面的区别，纯粹是常数优化；当 V·E 高达 10⁸ 时，常数可能决定生死。工程里如果瓶颈确实在 Bellman-Ford 上，可以按这个思路做一次机械优化，但先别过度设计：代码可读性通常比常数更值钱。

5.9 写完代码后，用三个最小用例自检

写任何图算法都建议配一组最小用例做冒烟测试，Bellman-Ford 尤其如此，因为它有“返回 null”的特殊路径。第一个用例是负权无负环：第 4 章那张 5 顶点图，期望返回 dist = [0, 4, 1, 3, 2]，且 prev 链从 T 回溯得到 S → A → B → C → T。第二个用例是负环：给同一张图加上一条 C→A 权重 −5 的边，构成 A→B→C→A 总权重 −3 的负环，期望函数返回 null。第三个用例是平凡边界：n = 1 的单顶点图，无任何边，期望返回 dist = [0]；n = 2 但只有一条 s 指向其他顶点的边，另一个顶点不可达，期望 dist 保持 ∞。

这三个用例分别覆盖“正常求解”“负环判定”“边界与不可达”，全部通过后，算法的主体逻辑基本可以放心。进阶做法是写一个暴力对拍器：对随机小图同时跑 Bellman-Ford 和 Floyd-Warshall（或暴力枚举所有简单路径），逐顶点比对距离；对拍几百组随机数据后，正确性信心会远超任何人工审查。第 9 篇我们提过对拍的理念，今天的主角同样适用——算法越朴素，对拍越容易。

6 负环检测：第 V 轮还能松弛，就出大事了

6.1 负环长什么样

先看一张有负环的图。S 到 A 的边权是 1，然后 A → B 权重 −2，B → C 权重 1，C → A 权重 −1：

graph LR
    S["S"] -->|"1"| A["A"]
    A -->|"-2"| B["B"]
    B -->|"1"| C["C"]
    C -->|"-1"| A
    style A fill:#ffd5d5
    style B fill:#ffd5d5
    style C fill:#ffd5d5

环 A → B → C → A 的总权重是 −2 + 1 + (−1) = −2，是一个货真价实的负环。它的可怕之处在于：每绕一圈，路径总代价减少 2。从 S 出发，路径 S → A 代价 1；绕一圈变成 S → A → B → C → A，代价 1 − 2 + 1 − 1 = −1；再绕一圈变成 −3；绕十圈变成 −19。只要体力无限，代价就能无限小。

6.2 第 V 轮为什么是“照妖镜”

回到代码：主循环刷完 V−1 轮后，我们再做一次全边扫描，如果还能松弛就报告负环。为什么这个判据如此干净？让我们反向推理。假如图中不存在负环，那么 3.1 节证明过：对每个顶点，都存在一条边数不超过 V−1 的最短路径；3.3 节的引理保证第 V−1 轮结束后，所有这样的路径都已被充分松弛，dist 不可能再变小。于是第 V 轮扫描必然一无所获——没有负环，就松弛不动。

假如图中存在从 s 可达的负环，情况恰好相反：负环可以让人无限绕圈，每绕一圈总代价更小，因此“最短路径”不存在有限答案，dist 可以无限变小。V−1 轮根本不可能“刷完”这种无限下降的过程，第 V 轮扫描时，负环上至少有一条边还能让 dist 继续缩小。于是“第 V 轮还能松弛 ⇔ 存在从 s 可达的负环”这个等价关系成立，算法用一轮扫描就完成了判案。

为了更直观，我们模拟一下负环检测时的 dist 变化。假设主循环跑满 4 轮（V = 5），负环上某个顶点 A 的距离被一轮一轮压低：1 → −1 → −3 → −5 → −7。注意这个数列没有下界，每一轮都在刷新，永远不会停止：

flowchart LR
    A1["dist[A] = 1"] --> A2["−1"]
    A2 --> A3["−3"]
    A3 --> A4["−5"]
    A4 --> A5["−7"]
    A5 --> A6["…… 每绕一圈少 2，没有下限"]
    style A6 fill:#ffaaaa

6.3 负环让“最短路径”失去意义

这是全篇最需要建立直觉的概念：负环不等于“路径很长但合法”，而是让最短路问题本身无解。通常我们说“最短路径”，隐含的期望是存在一条路径，它的总权重是所有路径中最小的。但负环破坏了“最小”的存在性：对任意一条从 S 出发、经过负环的路径 P，你总能沿着负环再绕一圈，得到一条总权重比 P 小 2 的路径 P′；P′ 还能再绕，无穷无尽。于是不存在“总权重最小的路径”，最短距离趋向负无穷，问题没有良好定义。

可以把这个区别记成一句话：负权边让算法变难，负环让答案消失。前者 Bellman-Ford 轻松应对，后者只能被检测、报告，而不能被“求解”。所以在竞赛和面试中，看到带负权的图，第一件事不是急着算距离，而是问自己：图里有没有负环？有，答案就是“无解”，或者题目要求你输出负环存在的标志；没有，Bellman-Ford 才能放心上岗。

6.4 可达性：不是所有负环都算数

检测代码里有个容易被忽略的限定词——“从 s 可达的负环”。如果负环存在于起点根本到不了的分量里，它对 dist 数组毫无影响，算法会照常返回正确的距离。举例：S 只能到达 A 和 B，而负环躲在 C、D 组成的孤立分量里，C、D 的 dist 永远是 ∞，第 V 轮检测时 dist[u] !== Infinity 会拦住它们，不误报。这通常是好事——单源最短路只需要关心从 s 能到达的部分。

但有些题目要求“全图是否存在负环”，不关心起点。两种经典处理：一是加一个虚拟超级源点，用 0 权边连到所有顶点，然后跑一次 Bellman-Ford，任何负环都变得可达；二是干脆把初始化改成“所有顶点 dist = 0”，效果等价——因为全 0 初始化相当于每个顶点都假装是起点，负环上的距离照样会被无限压低。后者实现更简单，是很多模板的标准做法，代价是失去“从某个特定起点出发”的距离语义。做题时先读清楚题目问的是“从 s 出发的最短路”还是“全图是否有负环”，再决定用哪种初始化。

6.5 负环检测的判据汇总

把第 6 章的结论压成一张表，方便复习：

这张表也是代码里 return null 语义的完整注脚。至此，Bellman-Ford 的“求解 + 判案”双职责已经全部讲完。下一章我们聊聊它的队列优化版 SPFA——一个工程与竞赛评价两极分化的算法。

6.6 数值边界：INF 怎么选，负数会不会溢出

不同语言对“无穷大”的处理方式不同，这里把数值边界的坑一次说清。JavaScript/TypeScript 里直接用 Infinity 最省心：任何有限数加 Infinity 还是 Infinity，不会溢出，也不用担心 dist[u] !== Infinity 的检查漏掉谁。但在 C++、Java 这类语言里，我们通常用一个很大的整数当 INF，比如 1e9 或 INT_MAX / 2。这时有两个隐患：一是 INF + w 可能溢出变成负数，让“不可达顶点”瞬间变成“距离 −2e9 的顶点”，整个算法被污染；二是 INF 太小可能真的比某些合法答案还小，导致正确答案被当成“不可达”跳过。惯例是取 LLONG_MAX / 4 或 1e18，并在松弛前显式判断 if (dist[u] == INF) continue，双保险。

另一个数值话题是负环检测与极大负数。如果边权可以到 −10¹⁸ 量级，V−1 轮累加后 dist 可能远超 32 位整数范围，所以涉及负权时优先用 64 位整数或浮点数。特别地，外汇套利场景里的权重是 −ln(rate)，是小浮点数，累积误差在汇率接近 1 时可能造成误判；工程上通常会加一个很小的容差 ε（比如 1e−9），或者用高精度十进制库。数学上 Bellman-Ford 对浮点依然成立，但“第 V 轮还能松弛”的判据在浮点世界里要小心：因为舍入误差，理论上无负环的图也可能出现 1e−12 级别的“伪更新”，导致误报。处理方法是把比较条件改成 dist[u] + w < dist[v] - EPS，给检测留一点余量。这个细节在竞赛里很少考，但在真实金融系统里能救命。

6.7 负环检测的两种问题形态

最后把“检测负环”在题目里的两种常见问法对齐一下。第一种问法：“从给定起点 s 出发，是否存在可达的负环？”这时用本文的模板即可：初始化只有 dist[s] = 0，第 V 轮扫描时只看 dist[u] !== Infinity 的边。第二种问法：“整张图是否存在负环？”这时要处理不可达分量——最简单的是把初始化改成所有顶点 dist = 0，然后照常刷 V−1 轮并检测；因为所有顶点都“假装是起点”，任何负环都会在检测轮现形。两种形态只有初始化不同，其余代码一字不差。做题时先翻译清楚题目问的是哪一种，再决定初始化，这是负环题最高频的失分点之一。

6.8 三种环的一分钟对比

这张表是 6.3 节的浓缩版。判断一个环“有没有害”，唯一标准是总权重的符号：正与零都无害（最多影响路径条数），负则致命。面试里如果有人拿“环”来考你，先问符号，再谈算法，顺序不能反。

7 SPFA：队列优化的 Bellman-Ford

7.1 观察：每一轮全图扫描，其实浪费了大多数边

Bellman-Ford 每一轮都要把全部 E 条边从头到尾扫一遍，但仔细想想，很多扫描是白做的：一个顶点 u 的 dist 根本没变，它的出边怎么可能带来新信息？只有“dist 刚被刷新”的顶点，才值得立刻把新距离传播给邻居。第 4 章的手算里，第 1 轮结束时只有 A 和 B 的 dist 变了，下一轮真正需要处理的其实就是 A 和 B 的出边，其他顶点（比如 T）虽然也被扫到，但全是无用功。这个观察催生了 SPFA（Shortest Path Faster Algorithm，最短路径快速算法）：用一个队列装“刚刚被更新”的顶点，只松弛它们的出边，直到队列为空。

7.2 SPFA 的工作原理

SPFA 的流程和 BFS 神似，但有一个关键区别：BFS 里每个顶点第一次入队就完成任务，SPFA 里一个顶点可以反复入队——每次它的 dist 被刷新，就重新入队，把新距离继续往后传。具体步骤：

1. 初始化 dist[s] = 0，其余为 ∞；队列里放入 s；用 inQueue 数组记录每个顶点是否已在队列中，避免重复排队。
2. 出队一个顶点 u，把 inQueue[u] 置为 false；遍历 u 的所有出边，尝试松弛邻居 v。
3. 如果 v 的 dist 被更新且 v 不在队列中，就把 v 入队。
4. 重复直到队列为空。

flowchart TD
    A["队列初始化：只有 s"] --> B{"队列为空？"}
    B -- "是" --> F["结束，dist 已收敛"]
    B -- "否" --> C["出队 u，标记不在队列"]
    C --> D["松弛 u 的全部出边"]
    D --> E{"有邻居 v 的 dist 被更新？"}
    E -- "否" --> B
    E -- "是" --> G{"v 已在队列中？"}
    G -- "是" --> B
    G -- "否" --> H["v 入队，count[v]++"]
    H --> B

对照第 4 章的手算：SPFA 在第 1 轮只处理 A、B 两个被更新的顶点，而不是把所有 6 条边都扫一遍；信息到达 T 时，T 立即入队处理，不会傻等下一轮的全图扫描。在“长得像稀疏图”的数据上，这个剪枝效果非常显著，平均复杂度接近 O(E)，比 Bellman-Ford 的 O(V·E) 快一大截——这正是“SPFA”这个名字里 Faster 的由来。

7.3 入队计数：SPFA 怎么检测负环

SPFA 检测负环的方式也很优雅：给每个顶点配一个计数器 count[v]，记录它入队的次数。正常图里，一个顶点的 dist 最多被刷新多少次？Bellman-Ford 的理论告诉我们，V−1 轮足够覆盖所有最短路，所以任何顶点最多入队 V−1 次（每轮最多被刷新一次）；一旦某个顶点的入队次数达到 V，说明存在负环——因为只有负环能让一个顶点被无限次刷新。代码上，在 v 入队时执行 count[v]++，若 count[v] >= n 就返回 null。

注意入队计数与 dist 刷新计数略有差别：一个顶点可能一次更新时已在队列里，不会重复入队，但它的 count 没有增加，仍然正确吗？严格分析会发现，用“入队次数”做判断在多数实现里已经足够，因为负环会让更新持续发生，顶点终将反复入队，count 迟早达到 V。更保险的写法是每成功更新一次就 count[v]++，不依赖是否已在队列——两种写法都能判负环，区别只在常数和边界语义，竞赛里都常见。

7.4 复杂度：平均很好，最坏很糟

SPFA 的时间复杂度是出了名的“薛定谔”：平均情况下接近 O(E)，配合邻接表在大规模稀疏图上跑得飞快；最坏情况下，精心构造的数据可以让它退化成 O(V·E)，甚至比朴素 Bellman-Ford 还慢（因为队列操作有额外常数）。业界流传着不少“卡 SPFA”的题：出题人故意构造一张图，让顶点反复入队，把队列操作拖到极限。所以严谨的说法是：SPFA 的期望复杂度 O(E) 是经验值，最坏复杂度 O(V·E) 是数学事实。

为什么最坏会这么糟？因为同一个顶点的 dist 可能被刷新非常多次，每次刷新都把它重新塞回队列，而每次出队都要扫描它的全部出边。在一个精心设计的图里，顶点 A 的 dist 可以按 100、99、98……一路缓慢下降，每降一次就入队一次，总入队次数可达 O(V·E) 量级。虽然负环检测的 count 数组保证了它不会无限循环，但“跑满 V 次入队才报错”本身就可能消耗巨大。

7.5 工程中的爱与恨：一句话定位

SPFA 在竞赛圈是“爱与恨交织”的选手：爱它的人享受它在随机数据上的飞一般速度，恨它的人被它最坏情况坑得超时。给它的最终定位一句话：SPFA 是 Bellman-Ford 的启发式优化，平均快、最坏不稳，适合需要负权/负环检测且数据不刻意针对它的场景；在严肃工程或对抗性数据里，宁可选择最坏复杂度有保证的 Bellman-Ford 或改用其他建模方式。如果你在刷题，先看数据范围和出题人风格：小图用朴素 Bellman-Ford 最稳，大图且要求负权处理时再考虑 SPFA，并做好被卡的觉悟。

7.6 SPFA 与朴素版的一轮对照

用第 4 章那张 5 顶点图做一次“同样输入、两种引擎”的对照，能直观感受 SPFA 的剪枝效果。朴素 Bellman-Ford 第 1 轮把 6 条边全部扫描，只有 A、B、C 三个顶点被刷新；第 2 轮又把 6 条边全扫一遍，刷新了 B 和 T；第 3 轮再扫 6 条边，刷新 C；第 4 轮再扫 6 条边，刷新 T。四轮下来共扫描 24 次边，其中大量检查是“dist 没变，白问一遍”。SPFA 则不同：队列初始只有 S，出队 S 松弛 S 的两条出边，A 和 B 入队；出队 A，只扫 A→B 这一条边，B 被刷新并入队；出队 B，扫 B→C 与 B→T 两条边……整个过程只处理“确实有变化的顶点”的出边，扫描的边数远小于 24。

但请注意，SPFA 省下的是“无效扫描”，不是“必要的松弛次数”。在精心构造的反例里，每个顶点的 dist 都可能被刷新极多次，SPFA 的入队与出队次数也会膨胀到 O(V·E)，和朴素版一个量级，还额外背着队列操作。所以正确的理解是：SPFA 是“平均情况下的工程优化”，不是“复杂度上的算法突破”；它的正确性继承自 Bellman-Ford，它的风险也完全继承自最坏情况。

7.7 SPFA 的两个经典工程优化：SLF 与 LLL

竞赛圈给 SPFA 配了两个著名的“外挂”，学有余力可以了解。SLF（Small Label First，小标签优先）：顶点 v 要入队时，如果 dist[v] 比当前队首顶点的 dist 还小，就把 v 插到队首，否则插到队尾——让“更有希望的顶点”优先被处理。LLL（Large Label Last，大标签最后）：出队时先看队首，如果它的 dist 大于当前队列所有顶点的平均 dist，就把它移到队尾，换一个更小的先出队。两个优化都能显著改善随机数据上的平均表现，但请注意：它们只改变处理顺序，不改变算法本质，最坏复杂度依然是 O(V·E)；构造数据同样能把它们卡死。

工程上的建议是：如果非要用 SPFA，至少加 SLF，代码量只多两行；但千万别把“加了优化的 SPFA”当成“复杂度保证 O(E)”的算法去宣传。在严肃系统里，最坏情况可预测的朴素 Bellman-Ford 或直接换建模方案，往往比一个平均快、最坏爆炸的算法更让人睡得着觉。这一节的一句话结论：优化是锦上添花，复杂度边界才是算法立身之本。

8 应用：外汇套利、差分约束与 Dijkstra 的禁区

8.1 外汇套利：把“乘法找环”变成“加法找负环”

Bellman-Ford 最著名的应用之一，是金融领域的外汇套利检测。假设有三种货币：美元 USD、欧元 EUR、英镑 GBP。汇率表告诉我们：1 美元可以换 0.9 欧元，1 欧元可以换 1.2 英镑，1 英镑可以换 1.1 美元。把货币当顶点、汇率当有向边的权重，这三个汇率正好构成一个环：

graph LR
    USD["美元 USD"] -->|"0.9"| EUR["欧元 EUR"]
    EUR -->|"1.2"| GBP["英镑 GBP"]
    GBP -->|"1.1"| USD

如果从 1 美元出发，走完这个环：1 × 0.9 × 1.2 × 1.1 = 1.188 美元。本金变成原来的 1.188 倍，白赚 18.8%！这种“绕一圈反而变多”的环就叫套利机会。问题来了：Bellman-Ford 检测的是“边权之和为负”的环，而这里汇率是乘法，环的总收益是乘积。怎么转化？取对数：对每条边，把权重 w 替换成 −ln(w)。于是环的“乘积大于 1”等价于“−ln 之和小于 0”，也就是一个负环。转化之后，检测外汇市场是否存在套利机会，就变成了标准的“全图是否存在负环”问题，直接交给 Bellman-Ford 即可。

这个例子的方法论价值远大于金融知识本身：任何“沿着环相乘越来越大的问题”，取对数后都可以变成“沿着环相加越来越小的负环问题”。同样的技巧也出现在概率图里“绕环乘积概率大于 1”等场景。看到“乘积、比例、倍数”这类词，第一反应就是对数化。

8.2 差分约束系统：把不等式变成最短路

差分约束系统（Difference Constraints）是一组形如 x_v − x_u ≤ w 的不等式，目标是判断是否存在一组实数解，并在有解时求出一组。它和最短路的关系只有一句话：把每个变量 x_i 当顶点，把不等式 x_v − x_u ≤ w 当成一条从 u 指向 v、权重为 w 的边，然后跑 Bellman-Ford——系统无解当且仅当图中存在负环，有解时 dist 数组本身就是一组可行解。

直觉是这样建立的：如果 dist 是从某个超级源点到各顶点的最短路，那么对任意边 (u, v, w)，最短路必然满足 dist[v] ≤ dist[u] + w，移项正是 x_v − x_u ≤ w。换句话说，最短路的三角不等式天然就是差分约束的候选解。若存在负环，则沿环累加不等式会得到 0 ≤ 负数 的矛盾，系统无解。差分约束在调度、区间覆盖、编译器指令调度等问题里经常出现，属于“一句话能讲清、考场上能救命”的经典转化。

graph LR
    U["u"] -->|"w"| V["v"]
    V -->|"约束：x_v − x_u ≤ w"| U

上面这张图左边是抽象的“变量 u → 变量 v”的边，右边标注它所代表的不等式；一组约束就是一整张图，Bellman-Ford 在这张图上决定系统是否有解。

8.3 Dijkstra 不适用，Bellman-Ford 上的场景清单

把“什么时候必须想起 Bellman-Ford”整理成清单：

第一，图里有负权边，且需要求单源最短路：Dijkstra 直接出局，Bellman-Ford 是标准答案。

第二，题目要求检测负环：这是 Bellman-Ford 独有的能力。Dijkstra 根本不会发现负环（它在非负权假设下压根不工作），BFS 和 Floyd 检测负环要么不适用、要么另有写法，单源负环检测首选 Bellman-Ford 或 SPFA。

第三，差分约束系统：不等式建模后必然出现任意符号的权重，而且“是否有解”恰恰等于“是否有负环”，Bellman-Ford 天然契合。

第四，外汇套利、概率环等乘积模型：对数化后变成负环检测，同上。

反过来说，如果图很大、边权非负、只求最短路，请坚持 Dijkstra；如果边权全为 1，BFS 更快。选型不是“哪个算法更高级”，而是“哪个算法恰好匹配问题的约束”。

8.4 两个实验室的一句话安利

理论再漂亮，不如亲手拖一拖图。我们的图论实验室支持你现场画一张带负权的图，观察每一轮松弛后哪些顶点的 dist 被刷新、第几轮收敛；而寻路实验室里你可以对比 BFS、Dijkstra、A* 的扩展过程，亲手验证“负权边会让 Dijkstra 定错案”这个结论。建议先画第 4 章那张 5 顶点图，再给它加一条负环边，看看 Bellman-Ford 的检测循环是怎么把负环揪出来的。

8.5 应用场景的现实边界

把应用收个尾，顺便给“Bellman-Ford 在真实世界用得少”这个印象正个名。在物理世界的网络里，边权（延迟、距离、成本）几乎不会为负，所以导航和路由协议清一色用 Dijkstra 家族；但只要模型里出现“收益”“差价”“概率”这类可正可负的量，负权就无处不在。金融套利是典型：汇率差可以让你越换越多；调度系统里“提前完成奖励”可以建模成负权边；游戏经济里“卖出回收”同理。这类问题的共同点不是“求最短”，而是“检测是否存在无限改进的循环”——恰好是 Bellman-Ford 第 V 轮扫描的看家本领。

所以更准确的说法是：Bellman-Ford 在“求最短路”的工程场景里不常见，在“检测负环”的建模场景里反而是主力。学算法时不要只背复杂度，还要记住每个算法“在什么抽象里出场”。差分约束把不等式变成图，套利把乘积变成和，检测问题把“无限改进”变成负环——这三个转化都指向同一个判据，而实现这个判据最直接的工具，就是今天的主角。

8.6 差分约束的一个完整小例子

光说不练不够，我们用一个三变量系统把差分约束走一遍。假设约束是：x₂ − x₁ ≤ 5，x₃ − x₂ ≤ −2，x₁ − x₃ ≤ 3。把每个不等式建成一条边：1→2 权重 5，2→3 权重 −2，3→1 权重 3。三个约束首尾相接构成环 1→2→3→1，总权重 5 + (−2) + 3 = 6 > 0，不是负环，系统有解。事实上取 x₁ = 0、x₂ = 5、x₃ = 3 就能同时满足三个不等式：5 − 0 = 5 ≤ 5 ✓，3 − 5 = −2 ≤ −2 ✓，0 − 3 = −3 ≤ 3 ✓。

现在把第一个约束改成 x₂ − x₁ ≤ −5，边 1→2 权重变成 −5，环的总权重变成 −5 + (−2) + 3 = −4 < 0。三个不等式相加得到 0 ≤ −4，显然是矛盾的，系统无解。Bellman-Ford 跑在这张图上，第 V 轮检测会发现这个 −4 的负环并报告无解——差分约束的“无解”和“负环”在数学上是同一件事。这个例子虽小，却完整展示了“不等式建模 → 建图 → 负环判无解 → dist 作解”的整条链路。

9 选型：BFS、Dijkstra、Bellman-Ford 与 Floyd，谁上场

9.1 四张牌的完整对比

把目前学过的四种最短路算法摆在一张桌上，按“边权要求、复杂度、能力、场景”四个维度对比：

这张表的阅读顺序应该是：先看问题要“单源”还是“全源”；再看向量是“边权非负”、“全相等”还是“有负数”；最后看要不要检测负环。四个条件一过，能用的算法往往只剩一两个。

9.2 决策树

把上面的对比压缩成一棵决策树，刷题时可以照着走：

flowchart TD
    Q1{"问题要求单源还是全源？"}
    Q1 -- "全源" --> FW["Floyd-Warshall（O(V³)，第 11 篇）"]
    Q1 -- "单源" --> Q2{"边权是否全为非负？"}
    Q2 -- "否" --> Q3{"是否还需要检测负环？"}
    Q3 -- "是" --> BF["Bellman-Ford（第 V 轮检测）"]
    Q3 -- "否" --> BF2["Bellman-Ford 或 SPFA"]
    Q2 -- "是" --> Q4{"边权是否全部相等？"}
    Q4 -- "是" --> BFS["BFS（O(V+E)）"]
    Q4 -- "否" --> DJ["Dijkstra（堆优化）"]

三个关键分叉依次是：全源还是单源、有没有负权、边权是否全等。把这三个问题刻进脑子，选型就不会再犹豫。特别提醒：“有负权但不需要检测负环”时，Bellman-Ford 依然是基准答案，SPFA 只是它的加速变体，不要为了“快”而放弃最坏复杂度保证。

决策树还有一个容易被忽略的分支：图很大、边权非负，但题目要求检测“是否存在负环”。这种要求本身自相矛盾——非负权图里根本不可能有负环，所以见到这种题，先确认读题无误，再按 Dijkstra 求解即可。反过来，图很大、边权可负、必须检测负环，这是最难受的组合：Bellman-Ford 的 O(V·E) 可能超时，SPFA 又怕被卡。实际竞赛里，这种组合通常伴随着特殊结构（比如边权有界、图是 DAG 或树），可以先拓扑排序或按结构剪枝，再决定要不要上负环检测。工程里也一样：先看数据形态，再选算法，永远比“背一个万能模板”可靠。把这些分支都装进决策树，选型才算完整。

9.3 一句话记忆

收束本节：BFS 数步数，Dijkstra 挑最小，Bellman-Ford 刷到底，Floyd 全源打表。四句口诀对应四种能力边界，也对应四篇图系列文章。Bellman-Ford 的位置很特殊：它几乎从不以“最快”著称，却以“最不挑食”著称——负权、负环、差分约束，凡是别的算法不敢接的活，它都敢接。

9.4 从第 8 篇到第 10 篇：最短路径的能力拼图

站到第 10 篇的高度回望，最短路径的能力拼图已经拼好一大半。第 8 篇我们用 BFS 拿下了无权图：每步代价相同，队列天然有序，O(V+E) 秒出答案。第 9 篇用 Dijkstra 拿下非负权图：只要边权不会“倒贴”，贪心定案就是安全的，堆优化让它能扛住十万级顶点。第 10 篇的 Bellman-Ford 把最后一块拼图补上：允许负权、允许检测负环，代价是 O(V·E)。三篇合起来，单源最短路径的所有边权情形都被覆盖了：

注意这张表不是“谁更强”的排名，而是“谁更合适”的索引：数据量决定复杂度预算，边权符号决定算法家族，问题形态（单源/全源）决定最后落谁。刷题时把这张表放在脑子里，比背十篇题解都管用。下一篇的 Floyd 会让我们第一次从“动态规划”的角度重看最短路，届时你会发现，Bellman-Ford 的“松弛”思想在 Floyd 的三层循环里以另一种形态再次登场——算法之间从来不是孤岛。

10 Bellman-Ford 要点速查表

把全文最重要的信息压进一张表，适合考前五分钟扫一眼：

这张表里最值得背的三行是：适用问题、V−1 轮的来由、第 V 轮判负环。背下这三行，就背下了 Bellman-Ford 的骨架。

11 自测题：七道题检验是否真的吃透

while (queue.length > 0) {
  const u = queue.shift()!;
  inQueue[u] = false;
  for (const [v, w] of graph[u]) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
      count[v]++;
      if (count[v] >= n) return null; // 负环
      if (!inQueue[v]) {
        queue.push(v);
        inQueue[v] = true;
      }
    }
  }
}

12 下一篇预告：《图系列第 11 篇：Floyd-Warshall》

到这里，图系列的单源最短路版图已经完整：无权图有 BFS，非负权图有 Dijkstra，负权图有 Bellman-Ford，负环有检测，SPFA 是加速变体。但你一定注意到了第 9 章选型表里的最后一个空格——全源最短路径：给定一张图，求任意两个顶点之间的最短距离。朴素做法是把每个顶点都当一次起点，跑 V 次单源算法；而更经典的答案，是那三层循环十几行代码的 Floyd-Warshall。

下一篇《图系列第 11 篇：Floyd-Warshall》，我们会用动态规划重新审视最短路径：定义“只允许经过前 k 个顶点作为中转”的递推式，推导出 O(V³) 的全源算法；看看它如何优雅地兼容负权边（只要没有负环），如何在跑完后顺手检查负环；再对比它和“跑 V 次 Bellman-Ford / Dijkstra”的复杂度与适用边界。Floyd 的代码可能是图论里最短的，但它的递推思想值得用一整篇来消化。

在等待下一篇的这段时间里，建议你把本文的速查表抄在一张卡片上，再亲手把第 4 章的手算图和 6.1 节的负环图各跑一遍代码——一次用“好边序”，一次用“坏边序”，对比收敛轮数；然后给负环图加一条从 S 到负环的 0 权边，观察 dist 如何无限下降。做完全部实验，Bellman-Ford 就不再是一个“背下来的模板”，而是你手里真正用得上的工具。咱们第 11 篇见。