13.4　负权边与 Bellman-Ford 简介

学习目标：学完本节，你能

• 说清 Bellman-Ford 的"$V-1$ 轮"是怎么来的，并证明它为什么够；
• 手写 Bellman-Ford，并用它算出 13.3 节 Dijkstra 算错的那个反例；
• 用"第 $V$ 轮还能不能松弛"判断负环，并说清这个判据为什么成立；
• 解释为什么 Bellman-Ford 的实际轮数由"边的给出顺序"决定（实测：同一个图差 7 倍）；
• 说出 SPFA 改进了什么、以及它为什么有争议。

先修：13.3（Dijkstra、松弛、负权反例）。 固定术语：松弛、最短路径、负环。 环境与版本：.NET 8 / C# 12。 预计阅读：32 分钟。

一、直觉：一个"笨办法"，但它不会错

13.3 节的教训是：Dijkstra 快，是因为它敢"确定" —— 取出当前距离最小的顶点，就宣布它的距离是最终答案，之后再也不改。

这个"敢"依赖边权非负。负权一来，它就错。

Bellman-Ford 走的是另一条路：干脆什么都不确定。

把所有的边，从头到尾扫一遍，每条边都尝试松弛一次。 这一整轮可能什么都没确定下来，那就再扫一轮。 扫到没有再发生变化为止 —— 但最多扫 $V-1$ 轮。

它没有任何"聪明"的地方：不做优先队列、不挑最小的、不提前下结论。每一轮就是把所有边摸一遍。

换来的是什么？

这就是本节的主题：用暴力换正确性。 代价是复杂度从"接近线性"掉到"$V$ 乘 $E$"。

二、形式化：为什么 $V-1$ 轮就够

先回答一个更基本的问题：为什么"扫到不变为止"一定会停？

关键引理：最短路径不会绕圈

如果图里没有负环，那么从 $s$ 到 $t$ 的最短路径一定是一条【简单路径】—— 不重复经过任何顶点。

为什么？ 假设最短路径重复经过了顶点 $x$：

  s → ... → x → ... → x → ... → t
             └── 中间这一段是个环 ──┘

把中间那段环去掉，路径更短（或至少不更长） —— 因为环的总权非负（无负环的前提）。 这与"它是最短路径"矛盾。所以最短路径不会重复顶点。

推论：一条简单路径最多有 $V-1$ 条边（$V$ 个顶点，最长的简单路径用完所有顶点）。

归纳：第 $k$ 轮确定"边数 ≤ k"的所有最短路

命题：跑完第 $k$ 轮后，所有"边数不超过 $k$"的最短路径都已经算出来了。

证明（对 $k$ 归纳）：

所以：跑完 $V-1$ 轮后，"边数 ≤ $V-1$"的最短路全部确定 —— 而无负环时，所有最短路径都满足这个条件。

这就是 $V-1$ 的来源。不是拍脑袋，是"最长简单路径的边数"。

注意这个证明里没有用到"边权非负" —— 它只用到了"无负环"。这正是 Bellman-Ford 能处理负权的原因。

一个实用的提前退出

如果某一轮扫下来，一条边都没能松弛 —— 说明已经收敛了，后面不可能再有变化，可以直接停。

if (!changed) break;      // 本轮一次松弛都没发生 -> 已经收敛

这个优化在实践中非常有效（下一节实测），但它不改变最坏情况。

三、实测一：轮数由"边的给出顺序"决定

一个自然的疑问：既然最多 $V-1$ 轮，那实际要跑几轮？

答案可能出乎意料：同一个图、同一批边，只把边的排列顺序换一下，轮数就差很多倍。

实测：图是一条链 $0 \to 1 \to \dots \to 7$（8 个顶点，每条边权 1），起点是 0。

  情形 A：边按【正序】给出（先 0->1，最后 6->7）
    第 1 轮后： 0  1  2  3  4  5  6  7
    第 2 轮后： 0  1  2  3  4  5  6  7   （本轮没有任何变化）
    -> 共 1 轮收敛

  情形 B：边按【逆序】给出（先 6->7，最后 0->1）
    第 1 轮后： 0  1  ∞  ∞  ∞  ∞  ∞  ∞
    第 2 轮后： 0  1  2  ∞  ∞  ∞  ∞  ∞
    第 3 轮后： 0  1  2  3  ∞  ∞  ∞  ∞
    第 4 轮后： 0  1  2  3  4  ∞  ∞  ∞
    第 5 轮后： 0  1  2  3  4  5  ∞  ∞
    第 6 轮后： 0  1  2  3  4  5  6  ∞
    第 7 轮后： 0  1  2  3  4  5  6  7
    -> 共 7 轮收敛

两边的边一模一样，只是排列顺序不同 —— 轮数差了 7 倍（= $V-1$）。

原因：在单独一轮里，信息只能沿着"这一轮中边的先后关系"往前传一跳。

• 正序时，边和路径方向一致：处理完 0→1 紧接着就是 1→2……一轮从头发到尾。
• 逆序时，处理 6→7 时 $dist[6]$ 还是 ∞，什么也做不了；每轮只能把已知信息往前推一条边。

所以"$V-1$ 轮"这个上界是真实可达的 —— 逆序的链状图就是它的实现。

这个事实引出了本节最后那个算法（SPFA）：既然每轮里大部分边都在做无用功，为什么不只处理"真正可能有变化"的那些边？

四、实测二：13.3 节那个反例，Bellman-Ford 怎么算对

用 13.3 节那张图（Dijkstra 在这里给出了错误的答案 3）：

    S --1--> A --1--> B --1--> T
    S --------5------> C --(-10)--> B

实测：

    第 1 轮后： 0  1 -5  5 -4
    第 2 轮后： 0  1 -5  5 -4   （本轮没有任何变化）

  收敛用了 1 轮（上限是 V-1 = 4 轮），有负环 = False
  dist[T] = -4

对照 13.3 节的实测：

看第 1 轮里发生了什么：

  S→A: 0 + 1  = 1                     → dist[A] = 1
  A→B: 1 + 1  = 2                     → dist[B] = 2
  S→C: 0 + 5  = 5                     → dist[C] = 5
  C→B: 5 + (-10) = -5  < 2            → dist[B] = -5   ★ 修好了
  B→T: -5 + 1 = -4                    → dist[T] = -4   ★ 顺着传下去了

关键在最后两行：$B$ 被改成 $-5$ 之后，同一轮里紧接着处理的 B→T 就用上了这个新值。

而 Dijkstra 在这里做的是：$B$ 早在几轮前就以 $2$ 出队并被"确定"了，B→T 用的是那个 2， 后面 $B$ 变成 $-5$ 时，那条边已经不会再被处理第二次。

Bellman-Ford 不设"已确定" —— 谁变了就重新松弛它的出边，所以错误传不下去。这就是"暴力"买到的正确性。

五、负环检测：第 $V$ 轮还能松弛

Bellman-Ford 还有第二项本事：它不仅知道"有负环"，判据还简单得离谱。

跑完 $V-1$ 轮后，再补扫一轮（叫"检测轮"）：

如果还能松弛，就说明存在负环；一轮都松弛不了，就说明没有。

为什么这个判据成立？ 直接来自第二节的归纳：

• 无负环 → 所有最短路径的边数都 $\le V-1$ → $V-1$ 轮后全部收敛 → 第 $V$ 轮不可能再松弛
• 有负环 → 沿着负环绕一圈距离就变小一点 → 永远存在"可以更小"的顶点 → 第 $V$ 轮必然还能松弛

实测（图：A → B(1)、B → A(-2)、A → T(1)，绕一圈总权 $-1$）：

    第 1 轮后：A=-1  B= 1  T= 0
    第 2 轮后：A=-2  B= 0  T=-1

  跑完 V-1 = 2 轮后，再补一轮【检测轮】：
    检测轮还能不能松弛？ 能 —— 判定为【有负环】

看 $A$ 的值：$0 \to -1 \to -2 \to \dots$ —— 每一轮都在变小，永远不会停。

这就是 13.3 节那个"惰性版 Dijkstra 出队 20 万次还在绕"的正式答案： 有负环的图根本不存在最短路径，任何"求最短路"的算法都只能检测并报错，不能给出答案。

Bellman-Ford 把这件事变成了一行代码 —— 这就是它在工程里不可替代的地方。

六、反预期实测：Bellman-Ford 其实不一定慢

教科书说 Bellman-Ford 是 $O(V \cdot E)$，"比 Dijkstra 慢得多"。 于是我在两张图上都测了一遍。

V = 5000：

  图 1：随机稀疏图（V = 5,000，30,000 条有向边）
    Bellman-Ford：实际 9 轮（上限 4,999 轮），耗时    0.46 ms
    SPFA        ：出队 9,311 次，耗时    0.29 ms
    Dijkstra    ：耗时    2.59 ms

  图 2：链状图 + 【逆序】边表（V = 5,000，4,999 条有向边）
    Bellman-Ford：实际 4,999 轮（= V-1，跑满上限），耗时   19.89 ms
    SPFA        ：出队 5,000 次，耗时    0.04 ms
    Dijkstra    ：耗时    0.03 ms

图 1 上，Bellman-Ford 比 Dijkstra 快了 5.6 倍。

这和教科书说的相反 —— 但两边都没错。

教科书说的是【复杂度上界】，图 1 揭示的是【实际轮数】。

图 1 是随机边序 —— 信息在几轮之内就传遍了整张图（实际只用了 9 轮，而上界是 4,999）。 每轮扫 30,000 条边 × 9 轮 = 27 万次操作，而且每次只是"加法 + 比较"，极简单。

Dijkstra 呢？ 它要做 3 万多次堆操作，每次 $O(\log V)$ 而且常数不小 —— 13.3 节刚测过：堆操作比数组扫描贵得多。

所以在这个规模上，Bellman-Ford 的"笨"反而赢了 Dijkstra 的"聪明"。

图 2 则是另一回事 —— 那是我在实验一里验证过的最坏情况（逆序边表 + 链状图）：

Bellman-Ford 在这里比 SPFA 慢了约 500 倍。 因为它的工作量是：

$$4{,}999 \text{ 轮} \times 4{,}999 \text{ 条边} \approx 2{,}500 \text{ 万次松弛尝试}$$

这一节的两个图，合起来才是完整的事实：

$O(V \cdot E)$ 是一个"最坏情况"上界，它会不会被触发，取决于【边的顺序】和【图的形状】。 随机图上它经常比 Dijkstra 还快；最坏情况下它慢两个数量级。

这也解释了为什么 13.1 节要我"如实呈现实测" —— 只报复杂度，你会以为 Bellman-Ford 永远不能用。

七、SPFA：把"扫全部边"换成"只扫刚变过的"

图 2 那 2,500 万次松弛里，绝大多数是无用功：

某一轮里，如果 $dist[u]$ 和上一轮一样没变，那么松弛 $u$ 的所有出边也不会产生任何新结果。

换句话说：只有"距离刚刚被改进过"的顶点，才值得再松弛它的出边。

把这句话变成代码，就是 SPFA（Shortest Path Faster Algorithm，由段凡丁在 1994 年提出）：

var queue = new Queue<int>();
queue.Enqueue(start);
inQueue[start] = true;

while (queue.Count > 0)
{
    int u = queue.Dequeue();
    inQueue[u] = false;

    foreach (var (v, w) in adj[u])            // ★ 只扫 u 的出边，不扫全图
    {
        if (dist[u] + w >= dist[v]) continue;
        dist[v] = dist[u] + w;                // 松弛成功

        if (!inQueue[v])                      // ★ 刚被改进 -> 入队，等会儿处理它的出边
        {
            queue.Enqueue(v);
            inQueue[v] = true;
        }
    }
}

它和 Bellman-Ford 的关系：

复杂度一样，实测差 500 倍 —— 因为最坏情况在 SPFA 上更难被触发。

但 SPFA 有争议

"SPFA 已死"是算法竞赛圈的一句名言。 原因是：

SPFA 的最坏复杂度并没有改善（还是 $O(V \cdot E)$），只是"平均情况"变好了。

而出题人可以专门构造一张图，让 SPFA 退化成和 Bellman-Ford 一样慢 —— 甚至更慢（还要多维护队列和 inQueue 数组）。

工程上的判断：

这条判断标准在本书里出现过很多次（6.3 节的哈希表、8.2 节的快排）： "平均快"和"最坏可控"是两件事，工程决策看的是后者。

八、练习

练习 13.4.1（手工跑 Bellman-Ford） 对下面的有向图，从 $S$ 出发跑 Bellman-Ford，写出每一轮结束后的 dist 数组：

  S --2--> A --(-3)--> B
  S --5--> B
  B --1--> T

(a) 需要几轮收敛？ (b) 最终 dist 是什么？ (c) 如果先处理 B→T，轮数会变吗？

练习 13.4.2（负环检测） 接上题，在图上再加一条边 B → S，权记为 $w$：

  S --2--> A --(-3)--> B
  S --5--> B
  B --1--> T
  B --w--> S      ← 新增的这条

(a) 图里出现了一个环，是哪一个？它的总权是多少（用 $w$ 表示）？ (b) $w$ 取什么值时，图里出现负环？ (c) 取 $w = -4$，Bellman-Ford 跑完 $V-1$ 轮后，检测轮第一次松弛的是哪条边？

练习 13.4.3（判断） 判断对错并说明理由： (a) Bellman-Ford 最多跑 $V-1$ 轮。 (b) 第 $k$ 轮结束后，所有"边数恰好为 $k$"的最短路径都确定了。 (c) 提前退出（某一轮没有变化就停）会改变最坏复杂度。 (d) SPFA 比 Bellman-Ford 快，是因为它的复杂度更低。

练习 13.4.4（工程判断） 一个汇率套利系统：顶点是货币，边 $A \to B$ 的权是 $-\log(\text{汇率})$，意思是"用 $A$ 换 $B$ 之后，购买力的对数值变化"。

(a) "从 USD 出发绕一圈回到 USD，购买力变多"这件事，在这个图里对应什么？ (b) 为什么这个问题必须用 Bellman-Ford 而不是 Dijkstra？ (c) 如果真的检测到了这样的环，业务上意味着什么？

九、练习答案

13.4.1

图：S→A(2)、S→B(5)、A→B(-3)、B→T(1)。边表按题面顺序给出。

(a) 2 轮收敛。

(b) 逐轮追踪：

第 2 轮一次松弛都没发生 → 收敛。

所以 dist = [S:0, A:2, B:-1, T:0]

(c) 会变。

注意第 1 轮里 A→B 那一步：$B$ 先被 S→B 松弛成 5，再被 A→B 松弛成 $-1$。

如果 B→T 排在 A→B 之前处理：

第二种顺序下，第 1 轮结束时 $dist[T] = 6$ 是过期的，要等第 2 轮处理 B→T 时才会被修正成 0。

这就是实验一那个现象的小型版：边序影响"信息在一轮内能传多远"，从而影响轮数。

注意：两者最终答案一样（Bellman-Ford 保证正确），差的只是"跑几轮"。

13.4.2

(a) 环是 $S \to A \to B \to S$，总权 $= 2 + (-3) + w = w - 1$。

图里只有这一个环（$T$ 是汇点，没有出边）。

(b) $w < 1$ 时出现负环。

因为负环的定义是"总权 $< 0$"：

$$w - 1 < 0 \iff w < 1$$

分三种情况：

注意中间那一行：零环不是负环，Bellman-Ford 在它上面会正常收敛。 "有环"和"有负环"是两码事 —— 这是本节最容易混淆的一处。

(c) 检测轮第一次松弛的是 S→A。

取 $w = -4$，图里 4 个顶点，所以 $V-1 = 3$ 轮。逐轮追踪（边按题面顺序处理）：

第 1 轮是怎么滚起来的（按边序）：

  S→A: 0 + 2  = 2        → dist[A] = 2
  S→B: 0 + 5  = 5        → dist[B] = 5
  A→B: 2 - 3  = -1  < 5  → dist[B] = -1
  B→T: -1 + 1 = 0        → dist[T] = 0
  B→S: -1 - 4 = -5  < 0  → dist[S] = -5     ★ 绕回起点了

检测轮一上来处理第一条边 S→A 就松弛成功了 —— 因为 $S$ 的距离已经被 B→S 又拉低到了 $-15$。

看最后三轮的 $S$：$0 \to -5 \to -10 \to -15$ —— 每绕一圈就少 5，永远不会停。

所以检测轮"必然还能松弛" —— 不是碰巧，而是沿着负环绕一圈，总有一条边能松弛。

13.4.3

(d) 是本节最容易搞混的一条 —— "实际更快"和"复杂度更低"是两回事。

这也是"SPFA 已死"那句话的由来：一个算法如果只有平均情况好，在需要确定性的场景里就不能作为依靠。

13.4.4

(a) 对应一个【负环】。

推导：

• 边权 $w(A \to B) = -\log(\text{汇率}_{A \to B})$
• 沿着一条路径走一圈，总权 $= -\log(\text{汇率}_1) - \log(\text{汇率}_2) - \dots = -\log(\text{汇率}_1 \times \text{汇率}_2 \times \dots)$
• 总权 $< 0$ $\iff$ $-\log(\text{连乘}) < 0$ $\iff$ $\log(\text{连乘}) > 0$ $\iff$ 连乘 $> 1$

所以"总权为负的环"恰恰就是"换一圈回来钱变多了" —— 这就是套利机会（arbitrage）。

(b) 因为要检测的就是负环，而 Dijkstra 在负权图上直接失效。

更重要的是：套利检测问的不是"最短路是多少"，而是"有没有负环" —— 这根本就不是 Dijkstra 能回答的问题类型。

(c) 业务上意味着"存在无风险的套利机会"。

具体来说：

这道题展示了"图论模型"的威力：一个金融问题，建模之后变成了"检测负环" —— 而后者是 Bellman-Ford 用一行代码就能回答的。

这也是本书反复出现的主题（12.4 节的排课、13.1 节的构建系统）： 难点往往不在算法，而在"把业务问题翻译成图"。

十、常见错误

十一、本节总结

1. Bellman-Ford 的思路：什么都不确定，把所有的边反复扫。 换来的是能处理负权 + 能检测负环。
2. $V-1$ 轮的来源：无负环时最短路径一定是简单路径，最多 $V-1$ 条边；第 $k$ 轮确定"边数 ≤ $k$"的最短路（归纳证明）。这个证明只用到了"无负环"，没用到"非负权" —— 这正是它能处理负权的原因。
3. 实测一：轮数由边的顺序决定。 同一个链状图，正序 1 轮收敛，逆序 7 轮（= $V-1$）。
4. 实测二：13.3 节那个 Dijkstra 算错的图（dist[T] = 3），Bellman-Ford 得到正确的 $-4$，1 轮就收敛。
5. 负环检测：跑完 $V-1$ 轮后再补一轮，还能松弛 ⟺ 有负环。
6. 反预期：教科书说它 $O(V \cdot E)$ 很慢，但实测随机稀疏图上比 Dijkstra 快 5.6 倍（0.46 ms vs 2.59 ms）—— 因为上界很少被触发，而且它的每次操作极其简单。
7. 但最坏情况是真的：逆序链状图上跑满 4,999 轮，19.89 ms，比 Dijkstra 慢约 660 倍。
8. SPFA = Bellman-Ford + 队列：只处理"刚被改进过"的顶点，实测在最坏情况图上快 500 倍（0.04 ms vs 19.89 ms）。但复杂度没变，"SPFA 已死"指的就是这个。

本章小结：第 13 章把"图上的路径问题"讲完了。

• 13.1 拓扑排序：只问"谁先谁后"，不问代价。Kahn 算法 / DFS 后序，$O(V+E)$。
• 13.2 无权最短路：BFS，前提是"所有边的代价相同"。多源 BFS、双向 BFS 是它的两个变体。
• 13.3 Dijkstra：BFS 把队列换成优先队列，能处理任意非负边权。贪心，"出队即确定"。
• 13.4 Bellman-Ford：什么都不确定，反复扫全部边，能处理负权、能检测负环。用 $O(V \cdot E)$ 换正确性。

贯穿本章的一条线索：

"换个容器" —— 队列 → 双端队列 → 优先队列 → 干脆不用容器。

每换一次，能表达的代价就更宽一档，代价是复杂度上升一档。

另一条线索是"边界意识"：

下一章衔接：本章的 Dijkstra 是一个贪心算法 —— 每一步都取当前距离最小的顶点，且从不后悔。

14.1 节会问一个更基本的问题：贪心什么时候是对的？

Dijkstra 的贪心靠"边权非负"撑着；13.1 节 Kahn 算法"随便挑哪个入度为 0 的都行"也是一种贪心（而且它永远对） —— 同样叫"贪心"，为什么有的万无一失、有的要附加条件、有的一败涂地？下一章回答。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "13.4",
  "title": "负权边与 Bellman-Ford 简介",
  "covered": [
    "Bellman-Ford 的「什么都不确定、反复扫全部边」思路与 Dijkstra 的对照表",
    "「无负环时最短路径一定是简单路径」引理与 V-1 轮的归纳证明",
    "提前退出优化（某一轮无松弛即收敛）",
    "反预期实测一：同一个链状图，正序 1 轮收敛、逆序 7 轮（= V-1）",
    "实测二：13.3 那个负权反例，Bellman-Ford 1 轮得到正确的 -4",
    "负环检测：第 V 轮还能松弛 ⟺ 有负环，及其由来",
    "反预期实测三：随机稀疏图上 Bellman-Ford 比 Dijkstra 快 5.6 倍",
    "最坏情况实测：逆序链状图跑满 4,999 轮、19.89 ms",
    "SPFA 的实现与「只处理刚被改进过的顶点」这一改动",
    "SPFA 的争议：复杂度未改善，只有平均情况变好",
    "汇率套利与负环检测的建模"
  ],
  "unresolved": [
    "最小生成树（Kruskal/Prim）超出本书范围",
    "Johnson 全源最短路超出本书范围",
    "A* 与地标预处理超出本书范围"
  ],
  "canonical_terms": {
    "松弛（Relaxation）": "尝试用「u 的已知距离 + 边 (u,v) 的权」改进 v 的已知距离，更小就更新",
    "负环（Negative Cycle）": "总权为负的环；存在负环时最短路径无解，只能检测并报错",
    "Bellman-Ford 算法": "反复扫描全部边做松弛、最多 V-1 轮的最短路算法，支持负权并检测负环",
    "SPFA": "Bellman-Ford 的队列优化版，只处理距离刚被改进过的顶点的出边"
  },
  "symbols_units": {
    "V": "顶点数",
    "E": "边数",
    "dist[v]": "从起点到 v 的当前已知最短距离"
  },
  "assumptions": [
    "读者已掌握 13.3 的松弛、Dijkstra 与负权反例",
    "本节的图都是有向图（无向图中一条负权边即构成负环）"
  ],
  "word_count_actual": 3518,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch13/Sec134/",
    "实验一：正序 1 轮、逆序 7 轮的逐轮 dist 数组为实测",
    "实验二：Bellman-Ford 1 轮得 dist[T]=-4，与 13.3 节 Dijkstra 的 3 对照，为实测",
    "实验三：负环检测轮判定「能松弛」，为实测",
    "实验四：随机图 0.46/0.29/2.59 ms、最坏图 19.89/0.04/0.03 ms，各跑 5 次取最快；跑 3 轮确认稳定（BF 随机图 0.45~0.46ms，Dijkstra 2.59~2.62ms）",
    "术语写法与 glossary.md 一致（松弛、最短路径、负权）"
  ],
  "known_issues": [
    "实验四初版 V=1500、图太小，三者的耗时都落到 0.0 ms（Stopwatch 精度不够），且链状图用了【正序】边表 —— 那不是最坏情况，Bellman-Ford 一轮就收敛了。改为 V=5000，并把链状图的边表改成逆序（实验一已证明这才是 V-1 轮的情形）",
    "初版把「随机稀疏图」预设成 Bellman-Ford 的劣势场景，实测它反而比 Dijkstra 快 5.6 倍 —— 如实改写正文，并把这个反预期作为本节的第三个实测发现",
    "未使用的常量 INF/Inf 触发 CS0219 警告，已删除",
    "练习 13.4.2 初稿写的是「把 S→B 的权从 5 改成 1」，但改完后那个图根本没有环，题目失去意义 —— 改为新增一条 B→S(w) 的边，让读者先推「环的总权 = w-1」，再判断 w<1 时才出现负环（顺带辨析正环/零环/负环）"
  ],
  "next": "14.1 贪心的适用条件"
}