Bellman-Ford算法

What · 是什么

Bellman-Ford 算法求解含负权边的单源最短路，并对『从源可达的负环』给出检测。核心是 n-1 轮全边松弛：每轮对所有边 (u,v,w) 尝试 dis[v] = min(dis[v], dis[u]+w)，第 n 轮仍能松弛说明存在可达负环。时间复杂度 O(VE)。它是 Dijkstra（只能非负权）无法覆盖场景的兜底算法，也是 SPFA、差分约束、Johnson 求势能的子程序。

Why · 为什么

How · 实现

伪代码

def bellman_ford(n, edges, s):
  dis[s]=0; 其余 INF
  for i in range(n):
    updated = False
    for (u,v,w) in edges:
      if dis[u]!=INF and dis[u]+w < dis[v]:
        dis[v] = dis[u]+w; updated=True
    if not updated: break
  # 第 n 轮检测负环
  for (u,v,w) in edges:
    if dis[u]!=INF and dis[u]+w < dis[v]:
      return 's 可达负环'
  return dis

Python 实现

def bellman_ford(n, edges, s):
    """含负权单源最短路 + 负环检测.
    n: 点数; edges: [(u,v,w)]; s: 起点 (0-indexed).
    返回 (ok, dis); ok=False 表示 s 可达负环, dis 无效."""
    INF = float('inf')
    dis = [INF] * n
    dis[s] = 0
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dis[u] != INF and dis[u] + w < dis[v]:
                dis[v] = dis[u] + w
                updated = True
        if not updated:
            break
    for u, v, w in edges:
        if dis[u] != INF and dis[u] + w < dis[v]:
            return False, dis
    return True, dis


def has_negative_cycle_global(n, edges):
    """全图负环检测: 加超级源点连 0 权边, 跑 Bellman-Ford"""
    super_edges = edges + [(n, i, 0) for i in range(n)]
    ok, _ = bellman_ford(n + 1, super_edges, n)
    return not ok


if __name__ == "__main__":
    # 标准用例
    edges = [(0, 1, 6), (0, 2, 7), (1, 2, 8), (1, 3, 5), (1, 4, -4), (2, 3, -3), (2, 4, 9), (3, 1, -2), (4, 0, 2), (4, 3, 7)]
    ok, dis = bellman_ford(5, edges, 0)
    assert ok and dis == [0, 2, 7, 4, -2], dis

    # 负环 (0 可达): 0->1(1),1->2(-3),2->0(1) 总 -1
    neg = [(0, 1, 1), (1, 2, -3), (2, 0, 1)]
    ok, _ = bellman_ford(3, neg, 0)
    assert ok is False
    # 无负环
    no_neg = [(0, 1, 1), (1, 2, -3), (2, 0, 5)]
    ok, dis = bellman_ford(3, no_neg, 0)
    assert ok and dis == [0, 1, -2], dis

    # 与 SPFA 交叉验证
    def spfa(n, edges, s):
        from collections import deque
        INF = float('inf')
        dis = [INF] * n
        cnt = [0] * n
        vis = [False] * n
        adj = [[] for _ in range(n)]
        for u, v, w in edges:
            adj[u].append((v, w))
        dis[s] = 0
        q = deque([s])
        vis[s] = True
        while q:
            u = q.popleft()
            vis[u] = False
            for v, w in adj[u]:
                if dis[u] + w < dis[v]:
                    dis[v] = dis[u] + w
                    cnt[v] = cnt[u] + 1
                    if cnt[v] >= n:
                        return False, None
                    if not vis[v]:
                        q.append(v)
                        vis[v] = True
        return True, dis

    import random
    random.seed(23)
    for _ in range(300):
        n = random.randint(1, 7)
        edges = []
        for i in range(n):
            for j in range(n):
                if i != j and random.random() < 0.3:
                    edges.append((i, j, random.randint(-5, 8)))
        s = random.randrange(n)
        ok1, d1 = bellman_ford(n, edges, s)
        ok2, d2 = spfa(n, edges, s)
        assert ok1 == ok2, (n, edges, s, ok1, ok2)
        if ok1:
            for i in range(n):
                assert d1[i] == d2[i], (i, d1[i], d2[i])
    print("All tests passed.")

易错点

• 第 n 轮判定负环时误认为『某边可松弛即全图负环』——只有 s 可达的负环才算
• 忘记 dis[u]==INF 时跳过（INF 参与运算会污染结果）
• 负环检测与最短路解耦：先判负环再输出 dis，否则 dis 无意义
• 边权很大的负值用 Python int 无溢出问题，但 INF 要足够大
• 邻接表实现时注意重边与自环；自环负权也是负环

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/shortest-path/
• CP-Algorithms✓ https://cp-algorithms.com/graph/bellman_ford.html
• 书籍✓ CPH ch13 pp133-142