数据结构与算法 / 系统课时

Bellman-Ford 解决什么问题

Bellman-Ford 解决什么问题

当图中存在负权边时,Dijkstra 的贪心前提可能失效。Bellman-Ford 通过反复松弛所有边计算单源最短路,并能判断从源点可达的负环,因此适合需要负权支持和负环检测的场景。

学习目标

  • 理解“松弛”为什么能逐步逼近最短距离,以及为何最多需要执行 V−1V-1 轮。
  • 能处理包含负权边的单源最短路,并识别从源点可达的负环。
  • 能根据 O(VE)O(VE) 的复杂度判断 Bellman-Ford 是否适合当前数据规模。

边松弛是算法的核心

设一条有向边为 u→vu \to v,权重为 ww。如果当前已经知道源点到 uu 的距离 dist[u],那么经过这条边到达 vv 的候选距离就是 dist[u] + w。当候选值更小时,就更新 dist[v],这一步叫松弛。

Bellman-Ford 不要求边权非负,因为它不会把某个顶点过早“定型”。算法每一轮都扫描全部边,让更短的路径继续向后传播。若图中不存在从源点可达的负环,一条最短简单路径最多包含 V−1V-1 条边,因此扫描 V−1V-1 轮已经足够。

Bellman-Ford 多轮松弛与负环检测流程

如果某一轮没有任何更新,可以提前结束,因为继续扫描也不会得到更短距离。

用额外一轮检测负环

完成最多 V−1V-1 轮后,再扫描一次全部边。如果仍有边可以被松弛,说明存在一条不断降低路径长度的回路,也就是从源点可达的负权环。此时“最短距离”本身没有有限下界。

这里的“可达”很重要:普通单源 Bellman-Ford 只会发现源点能够到达的负环。若要检测图中任意位置的负环,可以增加一个超级源点,并用权重为 0 的边连接所有顶点,再执行一次算法。

完整实现与验证

下面的 Python 示例同时返回最短距离和负环标记。示例图包含一条负权边,但没有负环。

python
from math import inf

def bellman_ford(n, edges, source):
    dist = [inf] * n
    dist[source] = 0

    for _ in range(n - 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

    for u, v, w in edges:
        if dist[u] != inf and dist[u] + w < dist[v]:
            return None, True

    return dist, False

def main():
    edges = [
        (0, 1, 4),
        (0, 2, 5),
        (1, 2, -2),
        (1, 3, 6),
        (2, 3, 3),
        (3, 4, 2),
    ]
    dist, has_negative_cycle = bellman_ford(5, edges, 0)
    printable = [None if d == inf else int(d) for d in dist]
    print("dist =", printable)
    print("negative_cycle =", has_negative_cycle)

if __name__ == "__main__":
    main()

预期输出

text
dist = [0, 4, 2, 5, 7]
negative_cycle = False

输出表明从顶点 0 到顶点 2 的最短路会利用权重为 -2 的边,因此距离从直接到达的 5 降为 2。把图改成含可达负环后,函数会返回 negative_cycle = True,而不会给出一组误导性的有限最短距离。

什么时候该选 Bellman-Ford

Bellman-Ford 的时间复杂度是 O(VE)O(VE),空间复杂度是 O(V)O(V)。它的优势不是速度,而是对负权边和负环的明确支持。

当边权全部非负时,通常优先考虑 Dijkstra;当图是 DAG 时,按拓扑序做松弛可在线性复杂度内完成;当图规模不大、存在负权边,或任务明确要求检测负环时,Bellman-Ford 更稳妥。算法选型的关键是先看边权约束和图结构,而不是只看“最短路”三个字。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Bellman-Ford 解决什么问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通