Bellman-Ford

Bellman-Ford 算法通过使用松弛操作来逐步更新节点的最短路径距离，并在第 V 次松弛操作后检测负权重环路。这使得它能够处理带有负权重边的图，并检测到负权重环路的存在。
时间复杂度为 O(V * E)。

伪代码:

for n-1 次：
  for 所有边(a,b,w)进行松弛操作:
   dist[b] = min(dist[b], dist[a] + w);

java 模板

class BellmanFord {
    
    public static void bellmanFord(int[][] edges, int n, int source) {
        // 初始化距离数组
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        // 迭代松弛操作（n-1）次
        for (int i = 0; i < n - 1; i++) {
            for (int[] edge : edges) {
                int u = edge[0];
                int v = edge[1];
                int w = edge[2];

                if (dist[u] != Integer.MAX_VALUE && dist[u] + w< dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        // 检测负权重环（第n次松弛操作还能更新）
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];

            if (dist[u] != Integer.MAX_VALUE && dist[u] + w< dist[v]) {
                System.out.println("存在负权环");
                return;
            }
        }

        System.out.println("起点到各个点的最短距离：");
        for (int i = 0; i < n; i++) {
            System.out.println("从" + source + "到" + i + "的最短距离为：" + dist[i]);
        }
    }

    public static void main(String[] args) {
        int V = 5; // 节点数量
        int[][] edges = {
            {0, 1, 4},
            {0, 2, 1},
            {1, 3, 1},
            {2, 1, 2},
            {2, 3, 5},
            {3, 4, 3},
            {4, 3, -2},
            {4, 0, 2}
        };
        BellmanFord1.bellmanFord(edges, V, 0);
    }
}