每日算法 — 使用java实现贝尔曼福特：负权边图最短路径与负环检测

引言

Dijkstra算法以贪心策略在正权图中高效求解单源最短路径，但遇到负权边时便束手无策。贝尔曼-福特（Bellman-Ford）算法通过动态规划的松弛思想，不仅能处理负权边，还能检测图中是否存在负权环——这是Dijkstra无法做到的。本文将用Java完整实现Bellman-Ford算法，深入讲解松弛操作、迭代更新与负环判定机制。

算法原理

Bellman-Ford算法的核心基于一个简单但深刻的观察：

在一个含有 (n) 个顶点的图中，任意最短路径最多包含 (n-1) 条边。

基于这一观察，算法进行 (n-1) 轮松弛（Relaxation）操作。每轮松弛遍历所有边，尝试用当前已知的最短路径更新各顶点的距离估计值。

松弛操作

对于边 ((u, v)) 权重为 (w)，若 (dist[u] + w < dist[v])，则更新 (dist[v] = dist[u] + w)。这表示”通过u到达v比当前已知路径更短”。

负环检测

若进行完 (n-1) 轮松弛后，仍存在可被松弛的边，则图中必然存在负权环——因为负环上的顶点距离可以无限减小。

Java实现

import java.util.*;

public class BellmanFord {

    /**
     * 图的边结构
     */
    static class Edge {
        int from;    // 起点
        int to;      // 终点
        int weight;  // 权重

        Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    /**
     * 最短路径结果
     */
    static class ShortestPathResult {
        int[] dist;        // 源点到各点的最短距离
        int[] predecessor; // 前驱节点，用于路径重建
        boolean hasNegativeCycle; // 是否存在负权环

        ShortestPathResult(int[] dist, int[] predecessor, boolean hasNegativeCycle) {
            this.dist = dist;
            this.predecessor = predecessor;
            this.hasNegativeCycle = hasNegativeCycle;
        }
    }

    /**
     * Bellman-Ford算法主实现
     * @param edges 图的边列表
     * @param n 顶点数量（顶点编号0到n-1）
     * @param source 源点
     * @return 最短路径结果
     */
    public static ShortestPathResult bellmanFord(List<Edge> edges, int n, int source) {
        // 初始化距离数组，源点距离为0，其余为无穷大
        int[] dist = new int[n];
        int[] predecessor = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(predecessor, -1);
        dist[source] = 0;

        // 阶段一：进行 n-1 轮松弛操作
        // 每轮遍历所有边，尝试更新最短距离
        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (Edge e : edges) {
                // 如果起点的距离已知（不是无穷大）
                if (dist[e.from] != Integer.MAX_VALUE) {
                    // 松弛条件：通过e.from到达e.to是否更短
                    if (dist[e.from] + e.weight < dist[e.to]) {
                        dist[e.to] = dist[e.from] + e.weight;
                        predecessor[e.to] = e.from;
                        updated = true;
                    }
                }
            }
            // 若本轮没有任何更新，提前终止（优化）
            if (!updated) {
                break;
            }
        }

        // 阶段二：负权环检测
        // 如果还能松弛，说明存在负权环
        boolean hasNegativeCycle = false;
        for (Edge e : edges) {
            if (dist[e.from] != Integer.MAX_VALUE &&
                dist[e.from] + e.weight < dist[e.to]) {
                hasNegativeCycle = true;
                break;
            }
        }

        return new ShortestPathResult(dist, predecessor, hasNegativeCycle);
    }

    /**
     * 重建从源点到目标点的最短路径
     */
    public static List<Integer> reconstructPath(int[] predecessor, int target) {
        List<Integer> path = new ArrayList<>();
        int current = target;
        while (current != -1) {
            path.add(current);
            current = predecessor[current];
        }
        Collections.reverse(path);
        return path;
    }

    /**
     * 打印结果
     */
    public static void printResult(ShortestPathResult result, int source, int n) {
        System.out.println("=== Bellman-Ford 最短路径结果 ===");
        System.out.println("源点: " + source);
        System.out.println("存在负权环: " + result.hasNegativeCycle);
        System.out.println();

        if (result.hasNegativeCycle) {
            System.out.println("警告：图中存在负权环，最短路径无定义！");
            return;
        }

        System.out.println("顶点\t最短距离\t路径");
        System.out.println("----\t--------\t----");
        for (int i = 0; i < n; i++) {
            String distStr = result.dist[i] == Integer.MAX_VALUE ? "∞" : String.valueOf(result.dist[i]);
            List<Integer> path = reconstructPath(result.predecessor, i);
            String pathStr = result.dist[i] == Integer.MAX_VALUE ? "不可达" : path.toString();
            System.out.printf("%d\t%s\t\t%s%n", i, distStr, pathStr);
        }
    }

    public static void main(String[] args) {
        // 示例1：包含负权边但无负权环的图
        System.out.println("【示例1：含负权边的图】");
        List<Edge> edges1 = new ArrayList<>();
        edges1.add(new Edge(0, 1, 4));
        edges1.add(new Edge(0, 2, 5));
        edges1.add(new Edge(1, 2, -3));
        edges1.add(new Edge(1, 3, 2));
        edges1.add(new Edge(2, 3, 1));
        edges1.add(new Edge(2, 4, 4));
        edges1.add(new Edge(3, 4, -2));

        ShortestPathResult result1 = bellmanFord(edges1, 5, 0);
        printResult(result1, 0, 5);

        // 示例2：包含负权环的图
        System.out.println("\n【示例2：含负权环的图】");
        List<Edge> edges2 = new ArrayList<>();
        edges2.add(new Edge(0, 1, 1));
        edges2.add(new Edge(1, 2, -1));
        edges2.add(new Edge(2, 0, -1)); // 0->1->2->0 总权重 -1，负权环

        ShortestPathResult result2 = bellmanFord(edges2, 3, 0);
        printResult(result2, 0, 3);

        // 示例3：经典货币套利检测场景
        System.out.println("\n【示例3：货币套利检测（负权环 = 套利机会）】");
        List<Edge> edges3 = new ArrayList<>();
        // 汇率对数转换后的权重：log(1/rate)
        // 若环上权重和 < 0，则存在套利
        edges3.add(new Edge(0, 1, -Math.log(0.8) > 0 ? 1 : -1)); // 简化示例
        edges3.add(new Edge(1, 2, 1));
        edges3.add(new Edge(2, 0, -3)); // 形成负权环

        ShortestPathResult result3 = bellmanFord(edges3, 3, 0);
        printResult(result3, 0, 3);
    }
}

复杂度分析

与Dijkstra的 (O((V+E)\log V)) 相比，Bellman-Ford的时间复杂度更高，但其能力更强：
– 处理负权边：Dijkstra的贪心策略在负权边下失效
– 检测负权环：这是Bellman-Ford独有的能力
– 分布式实现：每轮松弛可并行化，适合分布式系统

应用场景

1. 货币套利检测：外汇市场中，若一系列汇率换算后本金增加，即存在套利机会。将汇率取对数后转化为负权环检测问题。
2. 网络路由协议：RIP协议使用距离向量算法，其本质就是分布式Bellman-Ford，能适应拓扑变化。
3. 差分约束系统：将约束条件 (x_j – x_i \leq c_{ij}) 转化为图中的边，用Bellman-Ford求解可行性。
4. 时序约束验证：在实时系统中验证任务调度的时间约束是否可满足。

总结

贝尔曼-福特算法以最朴素的”反复尝试”方式，解决了Dijkstra无法触及的负权图问题。它的存在提醒我们：有时放弃贪心，选择更稳健的动态规划策略，才能处理更复杂的现实约束。负权环检测能力更使其成为金融套利检测、约束求解等领域不可或缺的工具。