Bellman-Ford 算法详解

Mohammed Islam Hadjoudj

资深运筹学工程师

1. Bellman-Ford 算法简介

Bellman-Ford 算法是图论中最基础的算法之一。它以先驱 Richard Bellman 和 Lester Ford Jr. 命名，二人于 20 世纪 50 年代末发表了该算法。它解决的是单源最短路径问题，也就是在带权图中，找出从一个起始节点到所有其他节点的最短路径。

如果你熟悉 Dijkstra 算法，也许会问：“为什么同一个问题还需要另一种算法？”答案在于其通用性。Dijkstra 算法在所有边权都为正的图（如实际道路网络）中更快、效率极高，但一旦引入负权边就会彻底失效。而 Bellman-Ford 则接纳负权重，并提供一套稳健的处理机制，即使在复杂的经济或网络场景中也能保证最短路径计算的准确性。

此外，Bellman-Ford 还有一项独门绝技：它能检测负环。负环是图中边权之和小于零的一个环路。如果存在这样的环，“最短路径”的概念就失去了意义，因为理论上可以无限次绕行该环，使路径长度趋于负无穷。Bellman-Ford 能检测出这种异常并提醒你，这使它成为金融套利等众多领域中异常检测的必备工具。

2. Dijkstra 的问题：负权重

要真正理解 Bellman-Ford 算法的必要性，我们必须先审视 Dijkstra 算法的关键局限。

Dijkstra 算法遵循贪心原则。它维护一组未访问节点，并在每一步选取距源点已知距离最小的节点。一旦某节点被选中，Dijkstra 就将其最短距离视为“已确定”，不再回头更新其距离。当所有边权为正时，这一假设完全成立，因为向路径添加一条边总会增加总路径长度。因此，之后发现的任何路径都不可能比当前已确定的更短。

然而，如果我们引入一条负权边，会发生什么？

考虑一个只有三个节点的简单图：A、B、C。起始节点是 A。

• 从 A 到 B 的边权重为 5。
• 从 A 到 C 的边权重为 10。
• 从 B 到 C 的边权重为 -8。

如果我们从 A 运行 Dijkstra 算法，它会先探索邻居 B（距离 5）和 C（距离 10）。下一个被确定的节点是 B，因为 5 小于 10。到 B 的最短距离现被锁定为 5。接着，它查看从 B 出发的边，看到 B 到 C 权重为 -8 的边。到 C 的新路径为 A -> B -> C，总权重为 5 + (-8) = -3。但 Dijkstra 算法是贪心的；如果它在意识到存在负权边之前就确定了 C，或者图更复杂，Dijkstra 就无法正确更新 C，从而返回错误结果。在更复杂的图中，Dijkstra“更长的路径不会变短”的贪心假设便会崩溃。

这正是 Bellman-Ford 的过人之处。它摒弃贪心策略，转而系统性地对所有边进行多轮松弛，从而保证即使某条负权边在后续过程中提供了更短的捷径，算法也能正确识别并更新最短路径。

3. 负环的危险

负环是图中的一个闭合回路，其构成环的各边权重之和小于零。这个概念是理解 Bellman-Ford 为何如此设计的根本。

设想一个图，节点 A、B、C 构成一个三角形。边权为 A 到 B（2）、B 到 C（-5）、C 到 A（1）。该环的总权重为 2 + (-5) + 1 = -2。若你想求从 A 到任何其他节点的最短路径，只需沿着这个环无限绕行即可。每绕一圈，总路径距离就减少 2。绕一圈后距离为 -2，绕十圈后为 -20。当趋于无穷时，最短路径便变为负无穷。

当存在一个从源点可达的负环时，最短路径问题无解。标准算法会陷入无限循环，不断试图找到“更短”的路径。Bellman-Ford 则优雅地避开了这一无限循环，并显式地检测出该环的存在。

4. 核心概念：边松弛

Bellman-Ford 算法的基础是一个称为边松弛的过程。这是算法用来更新到某节点已知最短距离的机制。

我们来定义两个数组（或字典）：

• distance[]：存储从起始节点到其他每个节点的已知最短距离。初始时，到起点的距离为 0，到所有其他节点的距离设为无穷大（∞）。
• predecessor[]（可选但有用）：存储在最短路径上紧位于某节点之前的节点。算法结束后可用它来重建实际路径。

从节点 u 到节点 v、权重为 w 的边，其松弛操作定义如下：

if distance[u] + w < distance[v]:
    distance[v] = distance[u] + w
    predecessor[v] = u

通俗地说：“如果到节点 u 的已知距离加上 u 到 v 的边权，小于当前已知到节点 v 的最短距离，那么我们就找到了一条更优的路径！更新到 v 的最短距离。”

Bellman-Ford 算法只是不断遍历图中所有的边，并一次又一次地尝试对它们进行松弛。

5. Bellman-Ford 的逐步执行

现在，我们来逐一走一遍算法的具体步骤。

设 V 为图中顶点（节点）数，E 为边数。该算法分三个主要阶段进行。

阶段 1：初始化

初始化 distance 数组。将到起始节点的距离设为 0，其余所有节点的距离设为无穷大。这表示起初我们不知道如何到达除起点之外的任何节点。

阶段 2：反复松弛

这是算法的核心。我们必须对图中所有的边进行松弛，并且要做 V - 1 次。

为什么恰好是 V - 1 次？考虑一个有 V 个节点的图。任意两节点之间最长的简单最短路径（不含任何环的路径）最多只有 V - 1 条边。在最坏情况下，需要对所有边完整迭代一次，才能保证长度为 1 条边的路径正确；两次迭代保证长度为 2 条边的路径正确，依此类推。因此，经过 V - 1 次迭代后，只要不存在负环，无论以何种顺序处理边，都能保证已找到到每个节点的绝对最短路径。

1. 启动一个运行 V - 1 次的循环。
2. 在该循环内部，遍历图中的每一条边。
3. 对每条权重为 w 的边 (u, v)，尝试对其松弛：若 distance[u] + w < distance[v]，则更新 distance[v]。

阶段 3：负环检测

完成阶段 2 后，在不存在负环的前提下，我们便得到了最短距离。为检测负环，我们对所有边再额外运行最后一次迭代。

1. 最后一次遍历每条权重为 w 的边 (u, v)。
2. 尝试对其松弛。如果 distance[u] + w < distance[v] 仍然成立，就意味着在 V - 1 条边之后我们还找到了更短的路径。
3. 对于简单路径而言，这在数学上是不可能的。唯一的解释是我们进入了一个可以无限减小距离的负权环。若出现这种情况，算法便终止并报告存在负环。

6. 实现与伪代码

Bellman-Ford 的精妙在于其简洁。它的实现非常直接，通常只是几层嵌套循环。以下是标准伪代码：

function BellmanFord(Graph, source):
    // 阶段 1：初始化
    distance = array of size |V|, filled with Infinity
    predecessor = array of size |V|, filled with Null
    distance[source] = 0

    // 阶段 2：对所有边松弛 |V| - 1 次
    for i from 1 to |V| - 1:
        for each edge (u, v) with weight w in Graph:
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                predecessor[v] = u

    // 阶段 3：检查负权环
    for each edge (u, v) with weight w in Graph:
        if distance[u] + w < distance[v]:
            return "错误：图中包含负权环"

    return distance, predecessor

这段代码与语言无关，可以轻松转写为 Python、C++、Java 或 JavaScript。

7. 时间与空间复杂度分析

尽管 Bellman-Ford 用途广泛，但与贪心算法相比，它在性能上有所代价。

• 时间复杂度：算法运行一个循环 V - 1 次，循环内部遍历所有 E 条边。因此，阶段 2 的时间复杂度为 O(V * E)。环检测阶段耗时 O(E)。总体时间复杂度为 O(V * E)。在 E 接近 V² 的稠密图中，复杂度趋近 O(V³)。这使它明显慢于 Dijkstra 算法——后者借助斐波那契堆可达到 O(V log V + E)。
• 空间复杂度：算法只需存储 distance 数组和 predecessor 数组，二者大小均为 V。此外还需存储图本身。因此，辅助空间复杂度为 O(V)。

由于其 O(V * E) 的时间复杂度，Bellman-Ford 通常只在必要时使用——也就是存在负权重、或必须检测负环时。对于严格为正的图，Dijkstra 才是首选。

8. 实际应用

尽管比 Dijkstra 慢，Bellman-Ford 在现实中却有着深远的应用，尤其是在网络与金融领域。

路由信息协议（RIP）

在计算机网络中，路由协议决定数据包如何在互联网上传输。最早、最著名的协议之一——路由信息协议（RIP）——是一种距离向量路由协议，它在很大程度上依赖 Bellman-Ford 算法的分布式变体。

在这种分布式架构中，路由器并没有整个网络的完整地图。相反，每台路由器只知道自己的直接邻居。路由器会定期与邻居共享其路由表（即它们已知的到各目的地的最短距离）。当一台路由器收到更新时，它使用 Bellman-Ford 松弛方程来更新自己的路由表。随着时间推移，这些信息在网络中传播，使所有路由器都收敛到最短路径。

金融套利检测

套利是指利用两个或多个市场之间的价格差异获利。在外汇（Forex）市场中，货币汇率不断波动。如果你能从一种货币出发，经过一连串其他货币的兑换，最终获得比起初更多的原始货币，而不承担任何市场风险，那就存在套利机会。

我们可以将货币汇率建模为一个图，其中节点是货币（USD、EUR、GBP 等），边代表汇率。由于我们是把汇率相乘而非相加，可以对汇率取负对数，将问题转化为可加形式。套利机会（即汇率乘积 > 1）在我们改造后的图中就会变成一个负环。在此图上运行 Bellman-Ford 便能检测出这些负环，为算法交易者即时识别出可获利的套利环路。

9. 学术资源与历史

Bellman-Ford 算法有时也称为 Bellman-Ford-Moore 算法，以表彰这三位计算机科学家各自独立的贡献：

• Alfonso Shimbel（1955）：最早提出了该算法，但流传不如后者广。
• Edward F. Moore（1959）：在 "The shortest path through a maze"（Proceedings of the International Symposium on the Theory of Switching）中发表了该算法的一个变体。
• Richard Bellman（1958）：在 "On a routing problem"（Quarterly of Applied Mathematics）中将其形式化。
• Lester Ford Jr.（1956）：在 "Network Flow Theory"（RAND Corporation Paper）中提出了奠基性概念。

该算法为动态规划奠定了基础——这一方法正是由 Richard Bellman 本人开创，并在数学、经济学和计算机科学中获得了广泛应用。