Bellman-Ford 算法详解：原理、代码与复杂度

Bellman-Ford 解决什么问题

Dijkstra 算法很快，但要求边权非负。有些问题天然带有负权：退款、货币兑换中的收益，或可以降到零以下的能耗。Bellman-Ford 能正确处理这类图，还能告诉你因负环而不存在最短路径的情况：沿着负环可以无限绕圈，代价越绕越小。

该算法以 Richard Bellman 和 Lester Ford Jr. 命名，二人在 20 世纪 50 年代分别发表了它的不同版本。

用大白话讲思路

1. 把起点的距离设为 0，其余所有节点设为无穷大。
2. 重复 V − 1 轮：对每条权为 w 的边 u → v，如果 dist[u] + w < dist[v]，就更新 dist[v]。
3. 再对所有边多做一轮。如果仍有距离被改进，就报告存在负环。

为什么是 V − 1 轮？不含环的最短路径最多包含 V − 1 条边。第 k 轮之后，所有最短路径至多有 k 条边的节点都已得到正确距离，所以 V − 1 轮就覆盖了每一条简单路径。

逐步演示一个例子

有向图含 4 个节点，边为 S→A（4）、S→B（5）、B→A（−3）、A→C（3）。每一轮都按这个顺序处理各条边。

第 1 轮中，A 先通过 S→A 变为 4，再通过 B→A 改进为 2，C 使用的是改进后的值。Dijkstra 算法会在查看 B 之前就把 A 确定为 4，这正是负权边造成的错误。

Python 实现

Bellman-Ford 直接处理普通的边列表，所以写起来很短：

def bellman_ford(nodes, edges, start):
    """edges: list of (u, v, weight). Returns dist, or raises on a negative cycle."""
    INF = float("inf")
    dist = {n: INF for n in nodes}
    dist[start] = 0
    for _ in range(len(nodes) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                         # already optimal
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            raise ValueError("graph contains a negative cycle")
    return dist
nodes = ["S", "A", "B", "C"]
edges = [("S", "A", 4), ("S", "B", 5), ("B", "A", -3), ("A", "C", 3)]
print(bellman_ford(nodes, edges, "S"))  # {'S': 0, 'A': 2, 'B': 5, 'C': 5}

添加一条权为 −6 的边 C → B，就形成了环 B → A → C → B，总权为 −3 + 3 − 6 = −6，因此多出的那一轮就能发现它：

try:
    bellman_ford(nodes, edges + [("C", "B", -6)], "S")
except ValueError as e:
    print(e)  # graph contains a negative cycle

dist[u] != INF 检查会跳过从尚未到达的节点出发的边。在 Python 中，float("inf") + w 仍是无穷大，所以这个检查主要是节省计算。在用大整数表示无穷大的语言里，它能防止溢出和错误更新。

时间与空间复杂度

在有 1,000 个节点、10,000 条边的图上，最多约需 1,000 万次松弛，所以当所有权非负时，Dijkstra 要快得多。

变体与常见错误

• 提前退出：某一整轮没有任何变化时就停止。这样做是安全的，实际中往往快很多。
• SPFA（最短路径快速算法）：用队列，只对距离发生变化的节点的出边重新松弛。通常很快，但最坏情况仍是 O(V × E)。
• 跳数受限的路径：恰好运行 k 轮，并使用上一轮距离的副本，就能得到至多 k 条边的最便宜路径，这可解决“k 次中转内的最便宜航班”。
• 找出环本身：保存父节点映射；当多出的那一轮更新了节点 v，沿父节点回溯 V 次必然落入环内，再继续走直到回到同一个节点。

何时使用及实际应用

• 当边权可能为负，或必须检测负环时，使用 Bellman-Ford；否则优先选择 Dijkstra。
• 距离向量路由协议（如 RIP）采用分布式 Bellman-Ford 的思想：每台路由器不断根据邻居的估计值更新自己的距离估计。
• 货币套利：把权设为 -log(rate)，负环就对应一串兑换操作，最终拿到的钱比开始时更多。
• Johnson 算法先运行一次 Bellman-Ford 对图重新赋权，之后就能从每个节点运行 Dijkstra，求出全源最短路径。
• 差分约束（形如 x - y <= c 的不等式组）可转化为最短路径问题来求解；出现负环则说明无解。