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

Bellman-Ford 算法

Bellman-Ford 算法

Bellman-Ford 用重复松弛处理含负权边的单源最短路径,并能判断源点可达区域是否存在负权环。本课将从松弛不变量出发,完成可运行实现并验证正常图与负权环图。

学习目标

  • 解释为什么最多需要进行 ∣V∣−1|V|-1 轮松弛。
  • 正确处理负权边、不可达顶点与距离上溢风险。
  • 检测从源点可达的负权环,并理解检测结果的边界。

问题定义

给定带权有向图 G=(V,E)G=(V,E) 和源点 ss,目标是计算 ss 到每个顶点的最短距离。与 Dijkstra 算法不同,Bellman-Ford 允许边权为负,因此适合汇率差、成本抵扣和差分约束等场景。

如果某个从 ss 可达的环总权重为负,沿该环反复行走会让路径长度不断减小,此时相关顶点不存在有限最短距离。算法除了计算距离,还必须报告这种负权环。

核心原理

松弛一条边 (u, v, w),就是检查“先到 u,再走到 v”是否更短:

dist[v] = min(dist[v], dist[u] + w)

一条不重复顶点的最短路径最多包含 ∣V∣−1|V|-1 条边。第 1 轮松弛能确定至多使用 1 条边的最优结果,第 kk 轮能传播至多使用 kk 条边的结果,因此完整扫描所有边 ∣V∣−1|V|-1 轮后,所有有限最短路径都已传播完成。

完成这些轮次后再扫描一次边。如果仍有可达边能够被松弛,说明存在从源点可达的负权环。不可达区域中的负权环不会影响当前源点,因此不会被报告。

Bellman-Ford 重复松弛与负权环检测

算法时间复杂度为 O(∣V∣∣E∣)O(|V||E|),距离数组和前驱数组的额外空间复杂度为 O(∣V∣)O(|V|)。若某一轮没有任何更新,可以提前结束,但最坏复杂度不变。

完整可运行示例

下面的 Java 17 程序先计算一个含负权边但无负权环的图,再验证一个从源点可达的负权环。使用 long 和足够小的哨兵值,避免把“无穷大”直接参与加法。

java
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,然后运行:

bash
javac BellmanFordDemo.java
java BellmanFordDemo

预期输出

text
无负权环图:
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 通过最多 ∣V∣−1|V|-1 轮全边松弛传播有限最短路径。
  • 额外一轮仍可松弛,等价于发现源点可达的负权环。
  • 可达性判断、哨兵值和整数范围是实现正确性的关键。

下一课预告

下一课将学习“Floyd-Warshall 算法”,把单源最短路径扩展为任意两点之间的最短路径,并用动态规划解释三重循环的顺序。

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

目录与阅读设置

阅读设置

17

记录一个想法

Bellman-Ford 算法

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

登录哪都通