每日算法 — 使用java实现全源最短路径：Floyd-Warshall动态规划与负环检测

在图论中，最短路径问题是最经典的应用场景之一。Dijkstra算法擅长解决单源最短路径，但当需要同时获取图中所有顶点对之间的最短距离时，Floyd-Warshall算法以其简洁的动态规划思想和优秀的编码实现成为首选。本文将用Java完整实现该算法，并深入讲解路径重建与负环检测两大扩展功能。

算法核心思想

Floyd-Warshall算法的精髓在于动态规划。它通过逐步引入”中间顶点”来更新最短路径。

假设图中顶点编号为 0 到 n-1，定义 dist[i][j] 为顶点 i 到顶点 j 的最短距离。算法的核心状态转移方程为：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

其中 k 作为中间顶点依次遍历 0 到 n-1。当所有中间顶点都被考虑过后，dist[i][j] 即为最终的最短距离。

关键点在于中间顶点的遍历顺序必须放在最外层循环，这样才能保证在更新 dist[i][j] 时，dist[i][k] 和 dist[k][j] 都已经考虑了所有编号小于 k 的中间顶点。

完整Java实现

以下代码实现了Floyd-Warshall算法，包含距离计算、路径重建和负环检测三大功能模块。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Floyd-Warshall全源最短路径算法实现
 * 支持：距离矩阵计算、路径重建、负环检测
 */
public class FloydWarshall {

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

    private final int n;              // 顶点数量
    private int[][] dist;             // 距离矩阵
    private int[][] next;             // 路径重建矩阵：next[i][j] 表示从i到j的最短路径上，i的下一个顶点
    private boolean hasNegativeCycle; // 是否存在负权环

    public FloydWarshall(int n) {
        this.n = n;
        this.dist = new int[n][n];
        this.next = new int[n][n];
        this.hasNegativeCycle = false;

        // 初始化距离矩阵：对角线为0，其余为无穷大
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
            Arrays.fill(next[i], -1);
        }
    }

    /**
     * 添加一条有向边
     * @param u 起点
     * @param v 终点
     * @param weight 边权（可为负数）
     */
    public void addEdge(int u, int v, int weight) {
        if (weight < dist[u][v]) {
            dist[u][v] = weight;
            next[u][v] = v; // 记录从u出发的下一个顶点
        }
    }

    /**
     * 执行Floyd-Warshall算法核心计算
     */
    public void compute() {
        // k作为中间顶点，必须放在最外层循环
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // 状态转移：经过k是否能缩短i到j的距离
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next[i][j] = next[i][k]; // 更新路径：从i出发先走next[i][k]
                    }
                }
            }
        }

        // 负环检测：若某个顶点到自身的距离变为负数，说明存在负权环
        for (int i = 0; i < n; i++) {
            if (dist[i][i] < 0) {
                hasNegativeCycle = true;
                break;
            }
        }
    }

    /**
     * 获取从u到v的最短距离
     * @return 最短距离，若不可达返回INF，若存在负环可能返回错误结果
     */
    public int getDistance(int u, int v) {
        return dist[u][v];
    }

    /**
     * 判断是否存在负权环
     */
    public boolean hasNegativeCycle() {
        return hasNegativeCycle;
    }

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

        List<Integer> path = new ArrayList<>();
        path.add(u);

        int at = u;
        while (at != v) {
            at = next[at][v];
            if (at == -1) {
                return Collections.emptyList(); // 路径断裂
            }
            path.add(at);
        }
        return path;
    }

    /**
     * 打印距离矩阵
     */
    public void printDistanceMatrix() {
        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) {
        // 构造一个有向带权图：城市间公路距离示例
        // 顶点0=A, 1=B, 2=C, 3=D
        FloydWarshall fw = new FloydWarshall(4);

        fw.addEdge(0, 1, 5);  // A -> B : 5
        fw.addEdge(0, 3, 10); // A -> D : 10
        fw.addEdge(1, 2, 3);  // B -> C : 3
        fw.addEdge(2, 3, 1);  // C -> D : 1
        fw.addEdge(1, 3, 9);  // B -> D : 9

        fw.compute();

        System.out.println("=== Floyd-Warshall 全源最短路径 ===\n");
        fw.printDistanceMatrix();

        System.out.println("\n具体路径示例：");
        List<Integer> path = fw.reconstructPath(0, 3);
        System.out.print("A到D的最短路径: ");
        for (int i = 0; i < path.size(); i++) {
            char city = (char) ('A' + path.get(i));
            System.out.print(city + (i < path.size() - 1 ? " -> " : ""));
        }
        System.out.println("，距离=" + fw.getDistance(0, 3));

        // 负环检测示例
        System.out.println("\n=== 负环检测示例 ===");
        FloydWarshall fw2 = new FloydWarshall(3);
        fw2.addEdge(0, 1, 1);
        fw2.addEdge(1, 2, -3);
        fw2.addEdge(2, 0, 1); // 0->1->2->0 的总权重 = -1，构成负环
        fw2.compute();
        System.out.println("图中是否存在负权环: " + fw2.hasNegativeCycle());
    }
}

路径重建原理

路径重建依赖 next 矩阵。next[i][j] 存储的是从顶点 i 到顶点 j 的最短路径上，i 应该走到的下一个顶点。

当初始化时，next[u][v] = v 表示直接从 u 到 v。当发现经过中间顶点 k 更短时，更新 next[i][j] = next[i][k]，意味着从 i 出发先按照到 k 的最短路径走。

重建路径时，从起点 u 出发，不断查询 next[当前][终点] 直到抵达终点。时间复杂度为 O(路径长度)。

负环检测机制

负权环是指环上所有边的权重之和为负数的环路。如果图中存在从某个顶点可达的负权环，则最短路径问题无意义（可以无限绕环使距离趋于负无穷）。

检测方法非常巧妙：Floyd-Warshall执行完毕后，检查所有 dist[i][i]。由于顶点到自身的初始距离为0，如果算法结束后 dist[i][i] < 0，说明存在一条从 i 出发回到 i 的负权路径，即存在负权环。

复杂度分析

与Dijkstra算法的对比：

• Dijkstra（堆优化）：时间复杂度 O((V+E)logV)，仅适用于非负权边，需执行V次才能得到全源结果
• Floyd-Warshall：时间复杂度 O(V³)，代码极简洁（三重循环），天然支持负权边（无负环时）

当顶点数 V < 200 且需要全源结果时，Floyd-Warshall因其简洁性和无需堆数据结构的优势，往往是工程实现的首选。

总结

Floyd-Warshall算法展现了动态规划的优雅力量：通过引入中间顶点这一维度，将复杂的图论问题分解为可递推的子问题。本文实现的Java版本完整覆盖了距离计算、路径重建和负环检测三大实用功能，可直接集成到路由计算、社交网络分析等实际项目中。