Bellman-Ford计算器

伪代码

Bellman-Ford 是一个用精巧换取通用性的最短路径算法。没有优先队列，也没有顺序上的抉择，只有对所有边的反复松弛。

BellmanFord(图, 源点):
    对每个结点 v: dist[v] = 无穷大
    dist[源点] = 0

    重复 V - 1 次:
        有改动 = 假
        对每条边 (u, v, w):
            若 dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                父结点[v] = u
                有改动 = 真
        若无改动: 退出            // 提前结束

    // 额外一轮用于检测负环
    对每条边 (u, v, w):
        若 dist[u] + w < dist[v]:
            报告存在可达的负环

不变式是：第 i 轮之后，所有至多使用 i 条边的最短路径都已正确。由于无负环图中的最短路径至多使用 V - 1 条边，V - 1 轮即可全部确定。若第 V 轮仍能改进，说明某条路径可以无限变短，而这正是负环的含义。

分步示例演算

从 A 出发，在一个含负权边、Dijkstra 会算错的图上运行 Bellman-Ford。边按下列固定顺序松弛。

示例图: 有向边 A 到 B (4)、A 到 C (5)、B 到 C (-3) 和 C 到 D (2)。

1. 初始化. dist = A 0，B 无穷大，C 无穷大，D 无穷大。
2. 第 1 轮. A 到 B 令 dist[B] = 4。A 到 C 令 dist[C] = 5。B 到 C 给出 4 + (-3) = 1，优于 5，因此 dist[C] = 1。C 到 D 令 dist[D] = 1 + 2 = 3。一轮之后：A 0、B 4、C 1、D 3。
3. 第 2 轮. 再次检查所有边，没有任何改进。有了提前结束的检查，算法在此停止，而不再执行剩余的轮次。
4. 负环检测. 对四条边再扫一遍，仍无改进，因此不存在从 A 可达的负环，距离已是最终结果。
5. 为什么 Dijkstra 在这里失败. Dijkstra 会在 C 离开优先队列时就把它确定为 5，因为它假定已确定的结点不会再改进。之后那条权重为 -3 的 B 到 C 的边便被忽略，Dijkstra 会给出 dist[C] = 5 和 dist[D] = 7，而不是正确的 1 和 3。

正确的距离是 A 0、B 4、C 1、D 3。仅仅一条负权边就足以让 Dijkstra 出错，这正是 Bellman-Ford 存在的理由。

复杂度及其来源

时间: O(VE) · 空间: O(V)

算法执行 V - 1 轮，每轮把 E 条边各松弛一次，因此为 O(VE)。空间是每个结点一个距离和一个父指针，即 O(V)，值得注意的是它与 E 无关。在 E 接近 V 的平方的稠密图上，时间趋近 O(V 的立方)，这也是 Bellman-Ford 只用于确实存在负权重场合的原因。提前结束的检查会在某一轮没有任何改动时停止，在真实图上往往几轮就结束，尽管最坏情况仍是 V - 1 轮。

何时使用贝尔曼-福特算法，何时不宜

Bellman-Ford 严格比 Dijkstra 更通用，也严格更慢。只有确实需要它带来的能力时才选它。

常见陷阱

• 只跑 V - 1 轮就收工. 没有额外的第 V 轮，就无法区分正确的距离与仍在通过负环不断下降的距离。这一轮检测不是可有可无的记账，而是让输出值得信赖的关键。
• 以为检测到的负环影响整个图. 额外那一轮只能检测从源点可达的环。位于不可达分量中的负环是看不见的，对单源问题而言也无关紧要。若你需要找出所有负环，可从一个连向每个结点的虚拟源点出发运行。
• 从距离为无穷大的结点做松弛. 在把无穷大表示为大整数而非浮点数的语言中，dist[u] + w 会溢出并变成负数，从而产生虚假的改进。请在松弛前检查 dist[u] 是否仍为无穷大。
• 出于保险在非负图上使用它. 在没有负权边的图上，Bellman-Ford 算出的结果与 Dijkstra 完全一致，但可能慢上几个数量级。通用性不是免费的。
• 在存在负环时仍期待最短路径. 当负环可达时，最短路径并非未知而是根本不存在：你总可以再绕一圈让代价更低。此时应报告该环，而不是返回一个距离。

常见问题

Bellman-Ford 算法有什么用？

它在可能含负权边的图中计算单源最短路径，并能检测负环。实践中它支撑 RIP 等距离向量路由协议、把汇率转换为负对数的货币套利检测，以及某些转移带来收益而非成本的调度问题。

为什么要用 Bellman-Ford 而不是 Dijkstra？

因为 Dijkstra 在含负权边时是错的。Dijkstra 在结点离开优先队列时就将其永久确定，假定此后没有任何东西能改进它，而之后发现的负权边打破了这个假设。Bellman-Ford 不做这样的承诺，因此保持正确，代价是 O(VE) 而非 O((V + E) log V)。

Bellman-Ford 如何检测负环？

经过 V - 1 轮松弛后，所有可能存在的最短路径都已确定，因为简单路径至多有 V - 1 条边。若再对所有边跑一轮仍能改进某个距离，那么这个改进只可能来自一个从源点可达、总权重为负的环。

Bellman-Ford 的时间复杂度是多少？

O(VE) 时间和 O(V) 空间。它对 E 条边执行 V - 1 轮。有了提前结束的优化，在真实图上往往早得多就结束，但最坏情况不变。在稠密图上这接近 O(V 的立方)。

Bellman-Ford 能处理负权重吗？

能，这正是它的全部目的，前提是不存在从源点可达的负环。有负权重但无负环时，它返回正确的最短路径。存在可达负环时最短路径根本不存在，算法会报告这一点，而不是返回一个无意义的距离。