Java实现Bellman-Ford算法：原理、步骤与负环检测

雨后青山

发布时间：2026-10-15 | 3人浏览过

原创

Bellman-Ford算法是处理含负权边图的最短路径问题的经典方案。它通过反复对图中所有边进行“松弛”操作来逐步逼近真实最短距离，其核心优势在于能够检测图中是否存在负权环。本文将解析其数据结构设计、松弛逻辑、Java代码实现以及针对正负环的测试结果。

算法核心原理

Bellman-Ford算法与Dijkstra算法都基于“松弛操作”，但策略不同。Dijkstra使用贪心策略选取当前最短节点，无法处理负权边；而Bellman-Ford则是对图中每条边重复进行松弛检查。

在一个拥有 n 个顶点的图中，如果不存在负权环，那么从源点到任意顶点的最短路径最多包含 n-1 条边。因此，算法需要对所有边进行 n-1 轮遍历和松弛更新。如果在第 n 轮遍历后，仍然存在可以被松弛的情况，则说明图中存在负权环（Negative Cycle），此时最短路径无下界。

该算法的时间复杂度为 O(n*m)，其中 n 为顶点数，m 为边数。虽然效率低于Dijkstra，但其通用性和负环检测能力使其在特定场景下不可或缺。

数据结构与操作步骤

第1步：构建边集数组

目的：支持边的快速遍历以进行全量松弛。

结构定义：由于需要遍历所有边，相比于邻接矩阵或邻接表，使用一维数组（Edge List）存储边更为直观且便于统一处理。每条边对象包含三个字段：起点 a、终点 b 和权重 w。

Java实现：使用静态数组 e[] 存储边，并维护一个计数器 cnt 记录当前边数。同时准备 dis[] 数组用于记录从源点到各点的最短距离初始值设为无穷大（0x3f表示近似最大值）。

class node {
    int a; // 起点
    int b; // 终点
    int w; // 权重
}

static node e[] = new node[210];
static int dis[] = new int[110]; // 距离数组
static int n, m; // 顶点数和边数
static int cnt = 0;

第2步：执行松弛操作

入口：对所有边进行迭代。

动作：对于每条边 e[j]（连接 a 到 b，权重 w），检查是否可以通过这条边缩短从源点到 b 的距离。判断条件如下：

dis[e[j].b] > dis[e[j].a] + e[j].w

若条件成立，则更新 dis[e[j].b] 的值为 dis[e[j].a] + e[j].w。这一过程即为“松弛”。在一次完整的边遍历中，如果有至少一次成功松弛，标记 flag = true。

第3步：迭代松弛 n-1 次

参数：外层循环次数由顶点数 n 控制。

逻辑：最坏情况下，最短路径信息需要经过 n-1 跳才能从源点传播到最远端。因此需将上述松弛操作执行 n-1 次。

优化：若在某一轮遍历中没有任何边被松弛（即 flag == false），说明所有最短距离已稳定，可提前结束循环，节省计算时间。

第4步：负环检测

判断标准：在第 n-1 次迭代完成后，再额外执行一次全量边遍历。

结果分析：如果这次遍历中仍能找到满足 dis[e[j].b] > dis[e[j].a] + e[j].w 的边并成功松弛，证明图中存在负权回路（Negative Cycle）。因为正常情况下 n-1 次迭代后不应再有更优路径发现。

Java完整实现

以下代码展示了如何使用上述逻辑实现 Bellman-Ford 算法。输入数据格式为：第一行顶点数 n 和边数 m，随后 m 行每行包含 u, v, w 表示从 u 到 v 的一条有向边及其权重。

package graph.bellmanford;

import java.util.Scanner;

public class BellmanFord {
    static node e[] = new node[210];
    static int dis[] = new int[110];
    static int n;
    static int m;
    static int cnt = 0;

    // 初始化边数组对象
    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new node();
        }
    }

    // 添加边方法
    static void add(int a, int b, int w) {
        e[cnt].a = a;
        e[cnt].b = b;
        e[cnt++].w = w;
    }

    // 核心算法：返回true表示有负环，false表示无负环且计算完成
    static boolean bellman_ford(int u) { 
        // 1. 初始化距离为无穷大
        for (int i = 0; i < dis.length; i++) {
            dis[i] = 0x3f;
        }
        dis[u] = 0; // 源点距离为0

        // 2. 执行 n-1 次松弛操作
        for (int i = 1; i < n; i++) {
            boolean flag = false;
            for (int j = 0; j < m; j++) 
                if (dis[e[j].b] > dis[e[j].a] + e[j].w) {
                    dis[e[j].b] = dis[e[j].a] + e[j].w;
                    flag = true;
                }
            // 如果没有发生松弛，提前退出
            if (!flag)
                return false;
        }

        // 3. 再执行一次检测负环
        for (int j = 0; j < m; j++) 
            if (dis[e[j].b] > dis[e[j].a] + e[j].w)
                return true; // 还能松弛，说明有负环

        return false;
    }

    // 输出结果
    static void print() {
        System.out.println("最短距离：");
        for (int i = 1; i <= n; i++)
            System.out.print(dis[i] + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        if (scanner.hasNextInt()) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            for (int i = 0; i < m; i++) {
                add(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
            }
            
            if (bellman_ford(1)) {
                System.out.println("有负环！");
            } else {
                print();
            }
        }
    }
}

class node {
    int a;
    int b;
    int w;
}