【数据结构与算法体系】之图算法（四）-所有结点对的最短路径问题

一、问题定义与应用背景

1.1 All-Pairs Shortest Paths (APSP)

给定带权有向图 $G = (V, E)$，其中 $|V| = n$，边权函数 $w: E \to \mathbb{R}$。

目标：对每对顶点 $(u, v)$（$u, v \in V$），计算从 $u$ 到 $v$ 的最短路径距离 $d(u, v)$ 和路径本身。

输出：一个 $n \times n$ 的距离矩阵 $D$，其中 $D[i][j] = \delta(i, j)$（从顶点 $i$ 到 $j$ 的最短距离）；以及一个 $n \times n$ 的前驱矩阵 $\Pi$，其中 $\Pi[i][j]$ 是 $i \to j$ 最短路径上 $j$ 的前驱顶点（用于路径重构）。

1.2 为什么需要专门的 APSP 算法？

“将单源最短路算法运行 $n$ 次”显然是可行的，但能否更高效？

• Dijkstra $n$ 次：$O(n \cdot (n+m)\log n) = O(n m \log n)$（二叉堆），$O(n m + n^2 \log n)$（斐波那契堆）
• Bellman-Ford $n$ 次：$O(n \cdot nm) = O(n^2 m) \approx O(n^4)$ 对稠密图
• Johnson 算法：$O(nm + n^2 \log n)$ 且支持负权边
• Floyd-Warshall：$O(n^3)$ 且极其简洁

对于稠密图（$m \approx n^2$），Floyd-Warshall 的 $O(n^3)$ 是最优的。对于稀疏图，Johnson 的 $O(nm + n^2 \log n)$ 更优。

---

二、Floyd-Warshall 算法

2.1 动态规划推导

设顶点集 $V = {1, 2, \ldots, n}$。定义子问题 $d_{ij}^{(k)}$：从顶点 $i$ 到顶点 $j$，中间顶点仅取自集合 ${1, 2, \ldots, k}$ 的最短路径长度。

初始条件（$k = 0$，无中间顶点）：
$$d_{ij}^{(0)} = \begin{cases} 0 & \text{if } i = j \ w(i, j) & \text{if } (i, j) \in E \ \infty & \text{otherwise} \end{cases}$$

递推公式（$k \geq 1$）：

对于最短路 $i \rightsquigarrow j$（中间顶点仅取自 ${1, \ldots, k}$），顶点 $k$ 要么在其中，要么不在：

• 若 $k$ 不在路径中：$d_{ij}^{(k)} = d_{ij}^{(k-1)}$
• 若 $k$ 在路径中：路径为 $i \rightsquigarrow k \rightsquigarrow j$，且中间 $i \rightsquigarrow k$ 和 $k \rightsquigarrow j$ 只使用 ${1, \ldots, k-1}$ 中的顶点（因为简单路径不重复经过 $k$），故 $d_{ij}^{(k)} = d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$

综上：

$$d_{ij}^{(k)} = \min\big( d_{ij}^{(k-1)}, ; d_{ik}^{(k-1)} + d_{kj}^{(k-1)} \big)$$

最终答案：$D[i][j] = d_{ij}^{(n)}$。

2.2 空间优化

观察递推式中 $d_{ij}^{(k)}$ 只依赖于 $d_{ij}^{(k-1)}, d_{ik}^{(k-1)}, d_{kj}^{(k-1)}$。关键洞察：**当计算 $d_{ij}^{(k)}$ 时，$d_{ik}^{(k)} = d_{ik}^{(k-1)}$ 且 $d_{kj}^{(k)} = d_{kj}^{(k-1)}$**，因为从 $i$ 到 $k$ 路径上 $k$ 不能是中间顶点（它已经是终点），同理 $k$ 到 $j$ 时 $k$ 是起点。

因此可以使用原地更新：一个二维数组就够了。

import java.util.*;

class FloydWarshall {
    static final int INF = Integer.MAX_VALUE / 2; // 避免加法溢出
    
    public static int[][] floydWarshall(int[][] graph, int n) {
        // dist[i][j] 初始化为直接边权重或INF
        int[][] dist = new int[n][n];
        int[][] next = new int[n][n]; // 用于路径重构
        
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }
        
        // 输入graph是邻接矩阵：graph[i][j] = 权重（无边则为INF）
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] != INF) {
                    dist[i][j] = graph[i][j];
                    next[i][j] = j; // i→j路径的下一个顶点
                }
            }
        }
        
        // Floyd-Warshall三重循环
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (dist[i][k] == INF) continue; // 剪枝
                for (int j = 0; j < n; j++) {
                    if (dist[k][j] == INF) continue; // 剪枝
                    int newDist = dist[i][k] + dist[k][j];
                    if (newDist < dist[i][j]) {
                        dist[i][j] = newDist;
                        next[i][j] = next[i][k]; // 路径更新
                    }
                }
            }
        }
        return dist;
    }
    
    // 重构从u到v的路径
    public static List<Integer> reconstructPath(int u, int v, int[][] next) {
        List<Integer> path = new ArrayList<>();
        if (next[u][v] == 0) return path; // 无路径
        path.add(u);
        while (u != v) {
            u = next[u][v];
            path.add(u);
        }
        return path;
    }
    
    // 检测负环
    public static boolean hasNegativeCycle(int[][] dist) {
        int n = dist.length;
        for (int i = 0; i < n; i++) {
            if (dist[i][i] < 0) return true; // 负环：自己到自己的距离 < 0
        }
        return false;
    }
}

2.3 复杂度分析

时间复杂度：三重嵌套循环，每层至多 $n$ 次迭代 → $\Theta(n^3)$。

空间复杂度：$\Theta(n^2)$（距离矩阵和前驱矩阵）。优化到原地更新后只需 2 个 $n \times n$ 数组。

2.4 正确性证明

定理：对任意 $k \in {0, \ldots, n}$，$d_{ij}^{(k)}$ 等于从 $i$ 到 $j$ 且中间顶点仅取自 ${1, \ldots, k}$ 的最短路径长度。

证明（对 $k$ 归纳）：

• 基底（$k=0$）：$d_{ij}^{(0)}$ 的定义直接满足。
• 归纳步：假设 $d_{ij}^{(k-1)}$ 正确。考虑任意 $i \rightsquigarrow j$ 路径（中间顶点 $\subseteq {1, \ldots, k}$）。分为两种情况：
  1. 路径不经过 $k$：长度为 $d_{ij}^{(k-1)}$（由归纳假设正确）
  2. 路径经过 $k$：路径可拆为 $i \rightsquigarrow k \rightsquigarrow j$。由于简单路径每个顶点最多出现一次，两端子路径的中间顶点均 $\subseteq {1, \ldots, k-1}$。由归纳假设和最优子结构，最短路径长度为 $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$。

取两者最小值即为 $d_{ij}^{(k)}$。$\square$

2.5 检测负权环

Floyd-Warshall 可以自然检测负权环：对任意顶点 $i$，若执行完毕后 $dist[i][i] < 0$，说明存在从 $i$ 出发回到 $i$ 的总权为负的环。

正确性：$dist[i][i]$ 初始为 0。在算法执行过程中，如果存在经过若干顶点的环且总权为负，该环会在某次迭代 $”闭合”$——当环上所有顶点都先后充当中继 $k$ 后，$dist[i][i]$ 会反映负环的存在。

2.6 示例演算

考虑带负权边但无负环的有向图：

0 → 1 (权 3)      0 → 3 (权 7)
1 → 2 (权 1)      2 → 0 (权 2)
2 → 3 (权 -2)     3 → 0 (权 4)

初始矩阵 $D^{(0)}$：

  0  1  2  3
0 0  3  ∞  7
1 ∞  0  1  ∞
2 2  ∞  0 -2
3 4  ∞  ∞  0

$k=0$ 轮后（中继顶点 ${0}$）：dist[1][3] 通过 0 可达，等等…
…最终 $D^{(4)}$：所有顶点对的最短距离确定。

---

三、Johnson 算法

3.1 核心思想

Johnson 算法的目标是让 Dijkstra（仅支持非负权）也能处理负权边。

核心技巧—重赋权（Reweighting）：为每个顶点 $v$ 引入一个势能（potential）$h(v)$，定义新的边权函数：

$$\hat{w}(u, v) = w(u, v) + h(u) - h(v)$$

关键性质 1：对于任意路径 $p = v_0 \to v_1 \to \cdots \to v_k$，重赋权后的路径长度与原始长度的关系：

$$\hat{w}(p) = \sum_{i=0}^{k-1} \hat{w}(v_i, v_{i+1}) = \sum_{i=0}^{k-1} [w(v_i, v_{i+1}) + h(v_i) - h(v_{i+1})] = w(p) + h(v_0) - h(v_k)$$

中间 $h(v_i)$ 项全部抵消（裂项相消 / telescoping sum），只剩下首尾势能。

关键性质 2：因此对于任意 $u, v$，$\hat{w}(p)$ 的最小化等价于 $w(p)$ 的最小化（因为 $h(u) - h(v)$ 对给定 $u, v$ 是常数）。即 $\hat{\delta}(u, v) = \delta(u, v) + h(u) - h(v)$。

3.2 构造使所有 $\hat{w}(u, v) \geq 0$ 的势能

加入一个超级源点 $s$（$s \notin V$），从 $s$ 向每个原始顶点连一条权为 $0$ 的边。在新图上运行 Bellman-Ford 算法，以 $s$ 为源点。设 $h(v) = \delta(s, v)$ 为从 $s$ 到 $v$ 的最短距离。

**证明 $\hat{w}(u, v) \geq 0$**：由三角不等式，$\delta(s, v) \leq \delta(s, u) + w(u, v)$，即 $h(v) \leq h(u) + w(u, v)$。重排得 $w(u, v) + h(u) - h(v) \geq 0$，即 $\hat{w}(u, v) \geq 0$。

如果 Bellman-Ford 检测到负环，算法终止（在负环图中最短路径无定义）。

3.3 完整 Java 实现

class Johnson {
    static final int INF = Integer.MAX_VALUE / 2;
    
    static class Edge { int u, v, w; Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; } }
    
    public static int[][] johnson(List<Edge> edges, int n) {
        // 步骤1：添加超级源点 n（编号从0开始，n即为超级源点）
        List<Edge> allEdges = new ArrayList<>(edges);
        for (int i = 0; i < n; i++) {
            allEdges.add(new Edge(n, i, 0)); // n → i 权0
        }
        
        // 步骤2：从超级源点运行Bellman-Ford
        int[] h = bellmanFord(allEdges, n + 1, n);
        if (h == null) {
            System.out.println("图中存在负权环！");
            return null;
        }
        
        // 步骤3：重赋权
        // 构建重赋权后的邻接表
        List<int[]>[] reweighted = new List[n];
        for (int i = 0; i < n; i++) reweighted[i] = new ArrayList<>();
        for (Edge e : edges) {
            int newW = e.w + h[e.u] - h[e.v];
            reweighted[e.u].add(new int[]{e.v, newW});
        }
        
        // 步骤4：对每个顶点运行Dijkstra
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(dist[i], INF);
        
        for (int src = 0; src < n; src++) {
            int[] d = dijkstra(reweighted, n, src);
            for (int tgt = 0; tgt < n; tgt++) {
                if (d[tgt] != INF) {
                    // 恢复原始距离
                    dist[src][tgt] = d[tgt] - h[src] + h[tgt];
                }
            }
        }
        return dist;
    }
    
    // Bellman-Ford 返回从源点到各顶点的最短距离
    private static int[] bellmanFord(List<Edge> edges, int n, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        
        // 松弛 n-1 轮
        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (Edge e : edges) {
                if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                    dist[e.v] = dist[e.u] + e.w;
                    updated = true;
                }
            }
            if (!updated) break; // 提前终止优化
        }
        
        // 第n轮检测负环
        for (Edge e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                return null; // 负环存在
            }
        }
        return dist;
    }
    
    // 标准Dijkstra（非负权）
    private static int[] dijkstra(List<int[]>[] graph, int n, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[]{src, 0});
        
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int u = cur[0], d = cur[1];
            if (d > dist[u]) continue; // 懒惰删除
            
            for (int[] edge : graph[u]) {
                int v = edge[0], w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }
        return dist;
    }
}

3.4 复杂度分析

• Bellman-Ford 一次：$O(n \cdot m)$
• 重赋权：$O(m)$ 扫描所有边
• Dijkstra $n$ 次：$n \cdot O(m \log n) = O(n m \log n)$（二叉堆）

总时间：$O(n m + n m \log n) = O(n m \log n)$（简化后）。若使用斐波那契堆实现 Dijkstra，则 $O(n m + n^2 \log n)$。

稀疏图（$m = O(n)$）：$O(n^2 \log n)$，显著优于 Floyd-Warshall 的 $O(n^3)$
稠密图（$m = O(n^2)$）：$O(n^3 \log n)$，比 Floyd-Warshall 的 $O(n^3)$ 多一个 $\log n$ 因子

3.5 势能法的推广

Johnson 的重赋权技巧并非单纯的算法实现细节，它是一种普适的势能方法（Potential Method）。在更一般的”最小费用流”问题中，同样的技巧被用作”reduced cost”来保证边权非负，从而能使用 Dijkstra 来寻找增广路。这种将可能包含负权的问题转化为非负权问题的思想在优化领域非常普遍。

---

四、重复 Dijkstra vs Floyd-Warshall vs Johnson

┌─────────────────┬──────────────┬────────────────┬──────────────┐
│     方法         │ 重复Dijkstra  │  Floyd-Warshall │   Johnson    │
├─────────────────┼──────────────┼────────────────┼──────────────┤
│ 时间复杂度       │ O(n·(n+m)logn)│    O(n³)       │ O(nm + n²logn)│
│ 负权边          │ ❌ 不支持     │ ✅ 支持(无负环) │ ✅ 支持(无负环)│
│ 负环检测        │ ❌           │ ✅ (diagonal<0) │ ✅ (BF阶段)   │
│ 实现复杂度       │ 简单         │ 非常简单        │ 复杂          │
│ 稠密图(m≈n²)    │ O(n³logn)    │ O(n³) 最优     │ O(n³logn)    │
│ 稀疏图(m≈n)     │ O(n²logn)    │ O(n³)          │ O(n²logn)    │
│ 额外空间        │ O(n+m)每轮   │ O(n²)          │ O(n+m)+O(n²) │
│ 路径重构        │ 可            │ 可(next矩阵)    │ 可(每轮D做)   │
└─────────────────┴──────────────┴────────────────┴──────────────┘

选择指南：

• 图很小（$n \leq 200$）且边权可能有负：Floyd-Warshall，三行核心循环，几乎不出错
• 图大且非负权、稀疏：重复 Dijkstra
• 图大、有负权、稀疏：Johnson
• 稠密图、有负权：Floyd-Warshall，恒定 $O(n^3)$

---

五、Floyd-Warshall 的变体与应用

5.1 传递闭包（Transitive Closure）

问题：给定有向图，判断任意两点间是否存在路径（不关心距离）。

Floyd-Warshall 将 dist[i][j] 改为布尔值 reach[i][j]：

boolean[][] transitiveClosure(boolean[][] graph, int n) {
    boolean[][] reach = new boolean[n][n];
    for (int i = 0; i < n; i++) System.arraycopy(graph[i], 0, reach[i], 0, n);
    
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
    return reach;
}

复杂度仍为 $O(n^3)$，但用 boolean 类型和位运算（Bitset）可大幅优化常数因子，做到每 64 位并行。

5.2 最小化最大边权路径（Minimax Path）

问题：找一条路径使得路径上最大边权最小。

将 Floyd-Warshall 的核心操作改为：dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]))

5.3 最长路径（Longest Path）——注意！

Floyd-Warshall 不能直接用来求最长路径，因为最长路径问题在一般图中是 NP-hard 的。Floyd-Warshall 仅在 DAG 上通过改为 max 操作求最长路径（此时等价于”求关键路径”），但 DAG 上的最长路径用拓扑排序做 $O(n+m)$ 更优。

---

六、面试常见追问

问题一：Floyd-Warshall 中的三重循环为什么必须是 k-i-j 顺序？交换循环顺序会怎样？

回答：k 必须是最外层循环，因为 Floyd-Warshall 的第 $k$ 轮迭代代表“允许中间顶点 ${1, \ldots, k}$”。如果 $k$ 不在最外层，那么在第 $k$ 轮还没处理完时就使用了包含 $k+1$ 在内中间顶点的路径信息，破坏了 DP 的阶段顺序。

具体来说，若把 $i$ 放在最外层：for(i) for(j) for(k)，则算法退化为重复单源最短路的错误实现——它不是 DP，而是对每个 $(i,j)$ 试图用任意顶点 $k$ 作为可能的中继。这可能得到正确结果，但需要运行足够的轮次（实际上要运行 $n$ 遍三重循环才能保证收敛），而非一遍即可。

若把 $j$ 放在最外层，同理。因此 $k$ 在最外层是 Floyd-Warshall 正确性的必要条件。

问题二：为什么要用 INF/2 而不是 Integer.MAX_VALUE？

回答：在实际实现中，我们需要检查 dist[i][k] + dist[k][j] < dist[i][j]。如果 dist[i][k] = Integer.MAX_VALUE 且 dist[k][j] > 0，则加法会导致整数溢出（在 Java 中变为负数），从而错误地”更新”dist[i][j]。使用 Integer.MAX_VALUE / 2（约 $10^9$）既足够大（大于任意实际可能的最短距离），又保证两个这样的值相加不会溢出（$2 \times 10^9 < 2^{31}-1 \approx 2.14 \times 10^9$）。这就是为什么在实现中需要使用 INF/2 或显式检查 dist[i][k] != INF。

问题三：给定 Floyd-Warshall 的结果矩阵，如何检测图中是否存在负权环？

回答：检查对角线上是否有负值。若存在 $i$ 使得 $dist[i][i] < 0$，则存在经过 $i$ 的负权环。原因是 $dist[i][i]$ 应当始终为 0（从自己到自己的距离为 0，不走任何边），但若存在一个从 $i$ 出发再回到 $i$ 且总权为负的环，则该环会使得 $dist[i][i]$ 被更新为负值。

注意：仅靠 $dist[i][i] < 0$ 检测负环的前提是图是强连通的（或至少 $i$ 能到达该负环并能回到 $i$）。若负环所在的 SCC 与 $i$ 不连通，需要在所有顶点上检查。更严谨的做法是：运行前令所有 $dist[i][i] = 0$，若运行后任意 $dist[i][i] < 0$，则存在负环。

问题四：Johnson 算法为什么比 “每个顶点跑一遍 Bellman-Ford” 好？

回答：Bellman-Ford 单次复杂度为 $O(nm)$，运行 $n$ 次为 $O(n^2 m)$。对稠密图（$m \approx n^2$），这是 $O(n^4)$，在实际中连 $n=100$ 都难处理。

而 Johnson 只运行 1 次 Bellman-Ford（$O(nm)$）+ $n$ 次 Dijkstra（$O(n(m + n)\log n)$）。对稀疏图，这大约等于 $O(n^2 \log n)$，远优于 $O(n^2 m) \approx O(n^3)$（稀疏时 $m=O(n)$）。

直观理解：Johnson 的聪明之处在于，它用 1 次 Bellman-Ford 的代价”消除”了所有负权边，然后就可以使用更快的 Dijkstra 做 $n$ 次。

问题五：动态图上的 APSP——如果图持续增加边，如何维护 APSP？

回答：这是一个活跃的研究领域。最基本的处理：

• **新加边 $(u, v)$ 权重 $w$**：对每一对 $(i, j)$，检查 $dist[i][u] + w + dist[v][j]$ 是否小于当前 $dist[i][j]$。一次更新 $O(n^2)$。
• 删除边：复杂得多，需要”备选路径”的概念。简单方案是重新计算 Floyd-Warshall。
• 动态图 APSP 的高效算法：Demetrescu 和 Italiano（2004）提出了 $O(n^2 \log^3 n)$ 每次更新的算法，但实现极为复杂。

---

七、总结

APSP 问题的三大算法各自展现不同的算法设计思想：

1. Floyd-Warshall：动态规划的最佳入门案例之一，$O(n^3)$ 时间 + $O(n^2)$ 空间，三行核心循环蕴含深刻的结构洞察。是稠密图和小规模图的首选。
2. Johnson：将”重赋权”的势能技巧发挥到极致——用一次 Bellman-Ford 为 Dijkstra 铺路。展示了不同算法通过巧妙组合获得理论上最优的复杂度。
3. 重复 Dijkstra：非负权图的最实用方案，$n$ 次 Dijkstra 简洁高效。

最后给一个实用的经验法则：

• $n \leq 200$：Floyd-Warshall（代码量最小）
• $n > 200$ 且无负权：重复 Dijkstra
• $n > 200$ 且有负权：Johnson
• 需要同时检测负环：Floyd-Warshall 或 Johnson

本篇是图算法系列中“最短路径”主题的第二篇，与本系列的【数据结构与算法体系】之图算法（三）-单源最短路径配合阅读，可建立完整的图最短路径知识体系。下一篇【数据结构与算法体系】之图算法（五）-最大流将进入网络流这一迷人领域。