每日算法 — 使用java实现Johnson算法：稀疏图全源最短路径与负权边处理

引言

在图论中，全源最短路径（All-Pairs Shortest Paths, APSP）问题要求计算图中任意两点之间的最短距离。Floyd-Warshall算法以O(V³)的复杂度解决这一问题，但在稀疏图上效率不高。Dijkstra算法虽然高效，却无法处理负权边。

Johnson算法巧妙地结合了Bellman-Ford和Dijkstra算法，在稀疏图上实现了O(V²logV + VE)的优秀复杂度，同时能够正确处理负权边（只要不是负权环）。本文将用Java完整实现这一经典算法。

算法核心思想

Johnson算法的核心步骤分为三步：

1. 添加虚拟源点：构造一个新图，添加一个虚拟源点s，从s到所有其他顶点添加权重为0的边。
2. 运行Bellman-Ford：从虚拟源点s运行Bellman-Ford算法，计算到所有顶点的最短距离h(v)。如果检测到负权环，则算法终止。
3. 重新赋权（Reweighting）：对每条边(u, v)，将其权重更新为 w'(u,v) = w(u,v) + h(u) – h(v)。这样所有边的权重变为非负。
4. 运行V次Dijkstra：在新的非负权图上，对每个顶点运行Dijkstra算法，得到全源最短路径。
5. 还原距离：将计算出的距离减去h(u)-h(v)的偏移量，得到真实最短路径。

重新赋权的数学原理：对于任意路径p = v₀→v₁→…→vₖ，有

[\sum_{i=1}^{k} w'(v_{i-1}, v_i) = \sum_{i=1}^{k} w(v_{i-1}, v_i) + h(v_0) – h(v_k)]

因此，新权重下的最短路径对应原权重下的最短路径。

Java完整实现

import java.util.*;

/**
 * Johnson算法实现稀疏图全源最短路径
 * 时间复杂度: O(V²logV + VE)
 * 空间复杂度: O(V²)
 */
public class JohnsonAlgorithm {

    // 表示无穷大
    private static final int INF = Integer.MAX_VALUE / 2;

    // 图的邻接表表示
    static class Edge {
        int to;      // 目标顶点
        int weight;  // 边权重

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

    static class Graph {
        int n;  // 顶点数
        List<List<Edge>> adj;  // 邻接表

        Graph(int n) {
            this.n = n;
            adj = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                adj.add(new ArrayList<>());
            }
        }

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

    /**
     * Johnson算法主入口
     * @param g 输入图
     * @return 全源最短路径矩阵，如果存在负权环返回null
     */
    public static int[][] johnson(Graph g) {
        int n = g.n;

        // Step 1: 添加虚拟源点，构建新图
        // 新图有n+1个顶点，第n个为虚拟源点
        Graph newG = new Graph(n + 1);
        for (int u = 0; u < n; u++) {
            for (Edge e : g.adj.get(u)) {
                newG.addEdge(u, e.to, e.weight);
            }
            // 从虚拟源点到所有顶点添加权重为0的边
            newG.addEdge(n, u, 0);
        }

        // Step 2: 运行Bellman-Ford计算h值
        int[] h = new int[n + 1];
        if (!bellmanFord(newG, n, h)) {
            System.out.println("图中存在负权环，无法计算最短路径");
            return null;
        }

        // Step 3: 重新赋权
        Graph reweighted = new Graph(n);
        for (int u = 0; u < n; u++) {
            for (Edge e : g.adj.get(u)) {
                // w'(u,v) = w(u,v) + h(u) - h(v)
                int newWeight = e.weight + h[u] - h[e.to];
                reweighted.addEdge(u, e.to, newWeight);
            }
        }

        // Step 4: 对每个顶点运行Dijkstra算法
        int[][] dist = new int[n][n];
        for (int u = 0; u < n; u++) {
            dijkstra(reweighted, u, dist[u]);
        }

        // Step 5: 还原真实距离
        // dist[u][v] = dist'[u][v] - h[u] + h[v]
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (dist[u][v] < INF) {
                    dist[u][v] = dist[u][v] - h[u] + h[v];
                }
            }
        }

        return dist;
    }

    /**
     * Bellman-Ford算法，检测负权环并计算最短距离
     * @param g 图（含虚拟源点）
     * @param source 源点
     * @param dist 距离数组（输出）
     * @return  true表示无负权环，false表示存在负权环
     */
    private static boolean bellmanFord(Graph g, int source, int[] dist) {
        int n = g.n;
        Arrays.fill(dist, INF);
        dist[source] = 0;

        // 松弛n-1次
        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (int u = 0; u < n; u++) {
                if (dist[u] == INF) continue;
                for (Edge e : g.adj.get(u)) {
                    if (dist[u] + e.weight < dist[e.to]) {
                        dist[e.to] = dist[u] + e.weight;
                        updated = true;
                    }
                }
            }
            if (!updated) break;  // 提前终止优化
        }

        // 检测负权环：再进行一次松弛
        for (int u = 0; u < n; u++) {
            if (dist[u] == INF) continue;
            for (Edge e : g.adj.get(u)) {
                if (dist[u] + e.weight < dist[e.to]) {
                    return false;  // 存在负权环
                }
            }
        }

        return true;
    }

    /**
     * Dijkstra算法（使用优先队列）
     * @param g 图（边权重非负）
     * @param source 源点
     * @param dist 距离数组（输出）
     */
    private static void dijkstra(Graph g, int source, int[] dist) {
        int n = g.n;
        Arrays.fill(dist, INF);
        dist[source] = 0;

        // 优先队列: (当前距离, 顶点)
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, source});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];

            // 跳过过期条目
            if (d > dist[u]) continue;

            for (Edge e : g.adj.get(u)) {
                if (dist[u] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[u] + e.weight;
                    pq.offer(new int[]{dist[e.to], e.to});
                }
            }
        }
    }

    /**
     * 打印距离矩阵
     */
    public static void printMatrix(int[][] dist) {
        int n = dist.length;
        System.out.println("全源最短路径矩阵:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] == INF) {
                    System.out.print("INF\t");
                } else {
                    System.out.print(dist[i][j] + "\t");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 构造测试图：5个顶点的稀疏图，含负权边
        Graph g = new Graph(5);
        g.addEdge(0, 1, 3);
        g.addEdge(0, 2, 8);
        g.addEdge(0, 4, -4);
        g.addEdge(1, 3, 1);
        g.addEdge(1, 4, 7);
        g.addEdge(2, 1, 4);
        g.addEdge(3, 0, 2);
        g.addEdge(3, 2, -5);
        g.addEdge(4, 3, 6);

        int[][] dist = johnson(g);
        if (dist != null) {
            printMatrix(dist);

            // 验证：0到2的最短路径应为0→4→3→2 = -4+6-5 = -3
            System.out.println("\n0到2的最短距离: " + dist[0][2] + " (预期: -3)");
            // 验证：1到4的最短路径应为1→3→0→4 = 1+2-4 = -1
            System.out.println("1到4的最短距离: " + dist[1][4] + " (预期: -1)");
        }

        // 测试负权环检测
        System.out.println("\n--- 负权环检测测试 ---");
        Graph cycleGraph = new Graph(3);
        cycleGraph.addEdge(0, 1, 1);
        cycleGraph.addEdge(1, 2, -3);
        cycleGraph.addEdge(2, 0, 1);  // 0→1→2→0 = -1，负权环

        int[][] cycleDist = johnson(cycleGraph);
        System.out.println(cycleDist == null ? "正确检测到负权环" : "检测失败");
    }
}

复杂度分析

与Floyd-Warshall的O(V³)相比，当图较为稀疏时（E << V²），Johnson算法具有显著优势。例如，对于一个有1000个顶点、5000条边的图，Johnson约需10⁷次操作，而Floyd-Warshall需要10⁹次。

应用场景

1. 交通网络分析：城市道路网络通常是稀疏图，且可能因拥堵费出现负权边。
2. 社交网络：计算任意两人之间的”距离”（如信任度、影响力传播）。
3. 网络路由协议：某些动态路由场景需要计算全源最短路径。

总结

Johnson算法通过重新赋权技术，巧妙地消除了负权边的影响，使得Dijkstra算法得以在全源最短路径问题中应用。它是稀疏图上计算全源最短路径的最佳选择之一，体现了算法设计中”问题转化”的核心思想。