每日算法 — 使用java实现Bellman-Ford算法：单源最短路径与负权边检测

在图论的最短路径问题中，Dijkstra算法以高效的优先队列实现著称，但它有一个前提条件——图中不能存在负权边。当业务场景涉及负权边（如金融套利、成本返利模型）或需要检测负权环时，Bellman-Ford算法便成为不可或缺的工具。本文将用Java完整实现该算法，并进一步讲解其队列优化版本（SPFA），帮助读者掌握从基础松弛到负环检测的全链路技术。

一、算法核心思想

Bellman-Ford算法的精髓在于松弛操作（Relaxation）。与Dijkstra的贪心策略不同，它采用迭代逼近的方式：通过多次遍历所有边，逐步缩短源点到各顶点的距离估计值。

1.1 松弛操作

对于一条从顶点 u 到 v、权重为 w 的边，松弛操作定义为：

if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
}

其含义是：如果发现经过 u 到达 v 的路径比当前已知路径更短，则更新 v 的最短距离。

1.2 迭代次数的数学保证

在一个包含 V 个顶点的图中，任意两点之间的最短路径最多包含 V-1 条边（无环时）。因此，算法只需进行 V-1 轮全局松弛：在第 i 轮中，所有最长为 i 条边的最短路径都会被正确计算出来。

1.3 负权环检测

若经过 V-1 轮松弛后，第 V 轮仍能松弛某条边，则说明图中存在可以从源点到达的负权环——因为绕环一圈总权重为负，每绕一次总距离都会减小，最短路径不存在有限值。

二、完整Java实现

以下代码实现了标准Bellman-Ford算法，包含距离计算、前驱节点记录、路径重建和负权环检测四大功能模块。

import java.util.*;

/**
 * Bellman-Ford单源最短路径算法实现
 * 支持：负权边、路径重建、负权环检测
 */
public class BellmanFord {

    // 表示无穷大（不可达）
    private static final int INF = Integer.MAX_VALUE / 2;

    // 边的内部类
    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;
        }
    }

    private final int n;          // 顶点数量
    private final List<Edge> edges; // 边列表
    private int[] dist;           // 距离数组
    private int[] prev;           // 前驱节点数组，用于路径重建
    private boolean hasNegativeCycle; // 是否存在负权环

    public BellmanFord(int n) {
        this.n = n;
        this.edges = new ArrayList<>();
        this.dist = new int[n];
        this.prev = new int[n];
        this.hasNegativeCycle = false;
    }

    /**
     * 添加一条有向边
     * @param from 起点
     * @param to 终点
     * @param weight 权重（可为负数）
     */
    public void addEdge(int from, int to, int weight) {
        edges.add(new Edge(from, to, weight));
    }

    /**
     * 执行Bellman-Ford算法核心计算
     * @param source 源点编号（0-based）
     * @return 若源点可达负权环返回false，否则返回true
     */
    public boolean compute(int source) {
        // 初始化距离数组：源点为0，其余为无穷大
        Arrays.fill(dist, INF);
        Arrays.fill(prev, -1);
        dist[source] = 0;

        // 第1轮：V-1次全局松弛
        // 每一轮至少确定一条最短路径上的一个顶点
        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (Edge e : edges) {
                // 如果from不可达，跳过（避免INF溢出）
                if (dist[e.from] == INF) continue;

                // 松弛操作：尝试通过e.from缩短到e.to的距离
                if (dist[e.from] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[e.from] + e.weight;
                    prev[e.to] = e.from; // 记录前驱，用于路径重建
                    updated = true;
                }
            }
            // 若本轮无任何更新，说明已收敛，提前退出
            if (!updated) break;
        }

        // 第2轮：负权环检测
        // 若还能松弛，则说明存在从源点可达的负权环
        for (Edge e : edges) {
            if (dist[e.from] == INF) continue;
            if (dist[e.from] + e.weight < dist[e.to]) {
                hasNegativeCycle = true;
                return false; // 发现负权环，最短路径无意义
            }
        }

        return true;
    }

    /**
     * 获取源点到目标点的最短距离
     * @param target 目标点
     * @return 最短距离，不可达返回INF，存在负权环时结果不可靠
     */
    public int getDistance(int target) {
        return dist[target];
    }

    /**
     * 判断是否存在从源点可达的负权环
     */
    public boolean hasNegativeCycle() {
        return hasNegativeCycle;
    }

    /**
     * 重建从源点到目标点的最短路径
     * @param target 目标点
     * @return 路径上的顶点列表（包含源点和目标点），不可达返回空列表
     */
    public List<Integer> reconstructPath(int target) {
        if (dist[target] == INF) {
            return Collections.emptyList();
        }

        LinkedList<Integer> path = new LinkedList<>();
        int at = target;
        // 沿前驱节点回溯到源点
        while (at != -1) {
            path.addFirst(at);
            at = prev[at];
        }
        return path;
    }

    /**
     * 打印所有顶点的最短距离
     */
    public void printDistances() {
        System.out.println("顶点\t最短距离\t前驱节点");
        for (int i = 0; i < n; i++) {
            String d = dist[i] == INF ? "INF" : String.valueOf(dist[i]);
            String p = prev[i] == -1 ? "None" : String.valueOf(prev[i]);
            System.out.printf("%d\t%s\t\t%s%n", i, d, p);
        }
    }

    public static void main(String[] args) {
        // 示例1：包含负权边的有向图
        // 顶点0为源点
        System.out.println("=== 示例1：含负权边的最短路径 ===");
        BellmanFord bf1 = new BellmanFord(5);
        bf1.addEdge(0, 1, 6);
        bf1.addEdge(0, 2, 7);
        bf1.addEdge(1, 2, 8);
        bf1.addEdge(1, 3, 5);
        bf1.addEdge(1, 4, -4);  // 负权边
        bf1.addEdge(2, 3, -3);  // 负权边
        bf1.addEdge(2, 4, 9);
        bf1.addEdge(3, 1, -2);  // 负权边（形成环 1->3->1，权重-7，负环！）
        bf1.addEdge(4, 0, 2);
        bf1.addEdge(4, 3, 7);

        boolean ok = bf1.compute(0);
        if (!ok) {
            System.out.println("图中存在从源点可达的负权环，最短路径无意义！");
        } else {
            bf1.printDistances();
            System.out.println("\n从0到4的最短路径: " + bf1.reconstructPath(4));
        }

        // 示例2：无负权环，可正常计算最短路径
        System.out.println("\n=== 示例2：无负权环的最短路径 ===");
        BellmanFord bf2 = new BellmanFord(4);
        bf2.addEdge(0, 1, 5);
        bf2.addEdge(0, 2, 3);
        bf2.addEdge(1, 2, -2); // 负权边，但无负环
        bf2.addEdge(1, 3, 1);
        bf2.addEdge(2, 3, 4);

        boolean ok2 = bf2.compute(0);
        if (ok2) {
            bf2.printDistances();
            System.out.println("\n从0到3的最短路径: " + bf2.reconstructPath(3));
            System.out.println("最短距离: " + bf2.getDistance(3));
            // 期望路径: 0 -> 2 -> 1 -> 3，距离 = 3 + (-2) + 1 = 2
        }
    }
}

三、SPFA队列优化

标准Bellman-Ford算法的时间复杂度为 O(V × E)，在稠密图（边数接近V²）时效率较低。SPFA（Shortest Path Faster Algorithm） 利用队列进行优化：只有当一个顶点的最短距离被更新时，它的出边才可能引发后续松弛，因此只需将这些”活跃”顶点入队处理。

import java.util.*;

/**
 * SPFA算法 - Bellman-Ford的队列优化实现
 * 平均时间复杂度接近O(E)，最坏仍为O(V * E)
 */
public class SPFA {

    private static final int INF = Integer.MAX_VALUE / 2;

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

    private final int n;
    private final List<List<Edge>> graph; // 邻接表
    private int[] dist;
    private int[] prev;
    private boolean hasNegativeCycle;

    public SPFA(int n) {
        this.n = n;
        this.graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        this.dist = new int[n];
        this.prev = new int[n];
    }

    public void addEdge(int from, int to, int weight) {
        graph.get(from).add(new Edge(to, weight));
    }

    /**
     * SPFA核心算法
     * @param source 源点
     * @return 是否存在负权环
     */
    public boolean compute(int source) {
        Arrays.fill(dist, INF);
        Arrays.fill(prev, -1);
        dist[source] = 0;

        // inQueue标记顶点是否在队列中，避免重复入队
        boolean[] inQueue = new boolean[n];
        // count[i]记录顶点i被松弛的次数，用于检测负环
        int[] count = new int[n];

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);
        inQueue[source] = true;
        count[source] = 1;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;

            for (Edge e : graph.get(u)) {
                if (dist[u] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[u] + e.weight;
                    prev[e.to] = u;

                    if (!inQueue[e.to]) {
                        queue.offer(e.to);
                        inQueue[e.to] = true;
                        count[e.to]++;

                        // 若某顶点入队超过V次，说明存在负权环
                        if (count[e.to] > n) {
                            hasNegativeCycle = true;
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    public int getDistance(int target) {
        return dist[target];
    }

    public boolean hasNegativeCycle() {
        return hasNegativeCycle;
    }

    public List<Integer> reconstructPath(int target) {
        if (dist[target] == INF) return Collections.emptyList();
        LinkedList<Integer> path = new LinkedList<>();
        int at = target;
        while (at != -1) {
            path.addFirst(at);
            at = prev[at];
        }
        return path;
    }

    public static void main(String[] args) {
        System.out.println("=== SPFA队列优化示例 ===");
        SPFA spfa = new SPFA(5);
        spfa.addEdge(0, 1, 6);
        spfa.addEdge(0, 2, 7);
        spfa.addEdge(1, 2, 8);
        spfa.addEdge(1, 3, 5);
        spfa.addEdge(1, 4, -4);
        spfa.addEdge(2, 3, -3);
        spfa.addEdge(2, 4, 9);
        spfa.addEdge(3, 1, -2);
        spfa.addEdge(4, 0, 2);
        spfa.addEdge(4, 3, 7);

        boolean ok = spfa.compute(0);
        System.out.println("负权环检测: " + (spfa.hasNegativeCycle() ? "存在" : "不存在"));
        if (ok) {
            for (int i = 0; i < 5; i++) {
                System.out.printf("到顶点%d的最短距离: %d%n", i, spfa.getDistance(i));
            }
        }
    }
}

SPFA的关键优化点

四、负权环检测的深层理解

4.1 为什么计数超过V次就说明有负环？

在无负环的图中，每个顶点的最短路径最多包含 V-1 条边，因此每个顶点最多被成功松弛 V-1 次。若某顶点第 V 次被松弛，说明找到了一条包含 V 条边的更短路径，根据鸽巢原理，这条路径必定重复经过某个顶点，即存在一个可达的环；而每次绕环总距离都在减小，故为负权环。

4.2 负权环对实际业务的影响

以货币套利场景为例：若将汇率取对数后作为边权重（-ln(rate)），负权环等价于绕一圈后本金增加的套利机会。Bellman-Ford算法的负环检测能力使其成为金融风控系统中识别异常套利路径的核心工具。

五、复杂度分析

选型建议：
– 图中有负权边但无负环 → 优先SPFA
– 需要严格最坏情况保证 → 标准Bellman-Ford
– 边权全非负 → Dijkstra
– 需要全源最短路径 → Floyd-Warshall（O(V³)）

六、应用场景

• 金融套利检测：通过汇率对数转换，利用负环检测发现套利路径
• 网络路由协议：RIP协议早期版本基于Bellman-Ford思想，处理跳数限制
• 差分约束系统：将约束条件转化为边，用Bellman-Ford求解可行性
• 物流成本优化：处理含返利、折扣等负成本边的运输网络

七、总结

Bellman-Ford算法以简洁的松弛迭代和强大的负权边处理能力，弥补了Dijkstra算法的局限性。本文实现的Java版本完整覆盖了标准算法、SPFA优化、路径重建和负环检测，读者可根据图的稀疏程度灵活选择实现方案。掌握该算法后，最短路径问题的技术栈将更加完善——从非负权的Dijkstra、全源的Floyd-Warshall，到支持负权的Bellman-Ford，三类算法各有其不可替代的应用边界。