数据结构与算法 / 系统课时
Bellman-Ford 算法
Bellman-Ford 算法
Bellman-Ford 用重复松弛处理含负权边的单源最短路径,并能判断源点可达区域是否存在负权环。本课将从松弛不变量出发,完成可运行实现并验证正常图与负权环图。
学习目标
- 解释为什么最多需要进行 轮松弛。
- 正确处理负权边、不可达顶点与距离上溢风险。
- 检测从源点可达的负权环,并理解检测结果的边界。
问题定义
给定带权有向图 和源点 ,目标是计算 到每个顶点的最短距离。与 Dijkstra 算法不同,Bellman-Ford 允许边权为负,因此适合汇率差、成本抵扣和差分约束等场景。
如果某个从 可达的环总权重为负,沿该环反复行走会让路径长度不断减小,此时相关顶点不存在有限最短距离。算法除了计算距离,还必须报告这种负权环。
核心原理
松弛一条边 (u, v, w),就是检查“先到 u,再走到 v”是否更短:
dist[v] = min(dist[v], dist[u] + w)
一条不重复顶点的最短路径最多包含 条边。第 1 轮松弛能确定至多使用 1 条边的最优结果,第 轮能传播至多使用 条边的结果,因此完整扫描所有边 轮后,所有有限最短路径都已传播完成。
完成这些轮次后再扫描一次边。如果仍有可达边能够被松弛,说明存在从源点可达的负权环。不可达区域中的负权环不会影响当前源点,因此不会被报告。

算法时间复杂度为 ,距离数组和前驱数组的额外空间复杂度为 。若某一轮没有任何更新,可以提前结束,但最坏复杂度不变。
完整可运行示例
下面的 Java 17 程序先计算一个含负权边但无负权环的图,再验证一个从源点可达的负权环。使用 long 和足够小的哨兵值,避免把“无穷大”直接参与加法。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BellmanFordDemo {
private static final long INF = Long.MAX_VALUE / 4;
record Edge(int from, int to, int weight) {
}
record Result(long[] distance, int[] predecessor, boolean hasReachableNegativeCycle) {
}
static Result bellmanFord(int vertexCount, List<Edge> edges, int source) {
long[] distance = new long[vertexCount];
int[] predecessor = new int[vertexCount];
Arrays.fill(distance, INF);
Arrays.fill(predecessor, -1);
distance[source] = 0;
// 每轮完整扫描所有边,让最短路信息继续向外传播一层。
for (int round = 1; round < vertexCount; round++) {
boolean updated = false;
for (Edge edge : edges) {
if (distance[edge.from()] == INF) {
continue;
}
long candidate = distance[edge.from()] + edge.weight();
if (candidate < distance[edge.to()]) {
distance[edge.to()] = candidate;
predecessor[edge.to()] = edge.from();
updated = true;
}
}
// 本轮没有更新时,后续轮次也不会产生新结果。
if (!updated) {
break;
}
}
boolean hasReachableNegativeCycle = false;
for (Edge edge : edges) {
if (distance[edge.from()] == INF) {
continue;
}
if (distance[edge.from()] + edge.weight() < distance[edge.to()]) {
hasReachableNegativeCycle = true;
break;
}
}
return new Result(distance, predecessor, hasReachableNegativeCycle);
}
static void printDistances(Result result, int source) {
for (int vertex = 0; vertex < result.distance().length; vertex++) {
long value = result.distance()[vertex];
String text = value == INF ? "INF" : Long.toString(value);
System.out.println(source + " -> " + vertex + " = " + text);
}
System.out.println("检测到可达负权环: " + result.hasReachableNegativeCycle());
}
public static void main(String[] args) {
List<Edge> normalGraph = List.of(
new Edge(0, 1, 6),
new Edge(0, 2, 7),
new Edge(1, 2, 8),
new Edge(1, 3, 5),
new Edge(1, 4, -4),
new Edge(2, 3, -3),
new Edge(2, 4, 9),
new Edge(3, 1, -2),
new Edge(4, 0, 2),
new Edge(4, 3, 7)
);
List<Edge> negativeCycleGraph = new ArrayList<>();
negativeCycleGraph.add(new Edge(0, 1, 1));
negativeCycleGraph.add(new Edge(1, 2, -1));
negativeCycleGraph.add(new Edge(2, 1, -1));
System.out.println("无负权环图:");
printDistances(bellmanFord(5, normalGraph, 0), 0);
System.out.println("负权环图:");
Result cycleResult = bellmanFord(3, negativeCycleGraph, 0);
System.out.println("检测到可达负权环: " + cycleResult.hasReachableNegativeCycle());
}
}将代码保存为 BellmanFordDemo.java,然后运行:
javac BellmanFordDemo.java
java BellmanFordDemo预期输出
无负权环图:
0 -> 0 = 0
0 -> 1 = 2
0 -> 2 = 7
0 -> 3 = 4
0 -> 4 = -2
检测到可达负权环: false
负权环图:
检测到可达负权环: true常见错误与练习
最常见的错误是直接计算 INF + weight,这可能溢出并制造虚假短路;必须先确认起点距离不是 INF。另一个错误是只松弛一次所有边,这只能传播一层路径信息。检测负权环时也要限定边的起点可达,否则会把无关连通分量误报为当前源点的问题。
练习 1:为示例补充路径还原功能。根据 predecessor 输出源点到顶点 4 的路径,验收结果应为一条总权重为 -2 的有效路径。
练习 2:构造一个与源点 0 不连通的负权环,验证程序仍输出 false;再添加一条从源点区域通向该环的边,验证结果变为 true。
本课总结
- Bellman-Ford 通过最多 轮全边松弛传播有限最短路径。
- 额外一轮仍可松弛,等价于发现源点可达的负权环。
- 可达性判断、哨兵值和整数范围是实现正确性的关键。
下一课预告
下一课将学习“Floyd-Warshall 算法”,把单源最短路径扩展为任意两点之间的最短路径,并用动态规划解释三重循环的顺序。