数据结构与算法 / 系统课时
Bellman-Ford 解决什么问题
Bellman-Ford 解决什么问题
当图中存在负权边时,Dijkstra 的贪心前提可能失效。Bellman-Ford 通过反复松弛所有边计算单源最短路,并能判断从源点可达的负环,因此适合需要负权支持和负环检测的场景。
学习目标
- 理解“松弛”为什么能逐步逼近最短距离,以及为何最多需要执行 轮。
- 能处理包含负权边的单源最短路,并识别从源点可达的负环。
- 能根据 的复杂度判断 Bellman-Ford 是否适合当前数据规模。
边松弛是算法的核心
设一条有向边为 ,权重为 。如果当前已经知道源点到 的距离 dist[u],那么经过这条边到达 的候选距离就是 dist[u] + w。当候选值更小时,就更新 dist[v],这一步叫松弛。
Bellman-Ford 不要求边权非负,因为它不会把某个顶点过早“定型”。算法每一轮都扫描全部边,让更短的路径继续向后传播。若图中不存在从源点可达的负环,一条最短简单路径最多包含 条边,因此扫描 轮已经足够。

如果某一轮没有任何更新,可以提前结束,因为继续扫描也不会得到更短距离。
用额外一轮检测负环
完成最多 轮后,再扫描一次全部边。如果仍有边可以被松弛,说明存在一条不断降低路径长度的回路,也就是从源点可达的负权环。此时“最短距离”本身没有有限下界。
这里的“可达”很重要:普通单源 Bellman-Ford 只会发现源点能够到达的负环。若要检测图中任意位置的负环,可以增加一个超级源点,并用权重为 0 的边连接所有顶点,再执行一次算法。
完整实现与验证
下面的 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()预期输出
dist = [0, 4, 2, 5, 7]
negative_cycle = False输出表明从顶点 0 到顶点 2 的最短路会利用权重为 -2 的边,因此距离从直接到达的 5 降为 2。把图改成含可达负环后,函数会返回 negative_cycle = True,而不会给出一组误导性的有限最短距离。
什么时候该选 Bellman-Ford
Bellman-Ford 的时间复杂度是 ,空间复杂度是 。它的优势不是速度,而是对负权边和负环的明确支持。
当边权全部非负时,通常优先考虑 Dijkstra;当图是 DAG 时,按拓扑序做松弛可在线性复杂度内完成;当图规模不大、存在负权边,或任务明确要求检测负环时,Bellman-Ford 更稳妥。算法选型的关键是先看边权约束和图结构,而不是只看“最短路”三个字。