Floyd-Warshall算法详解（Java实现多源最短路径问题完整教程）

算法核心思想

Floyd-Warshall算法基于动态规划的思想。它通过逐步引入中间节点来尝试缩短任意两点之间的路径。

假设我们有一个图，包含 n 个顶点，编号为 0 到 n-1。我们维护一个二维数组 dist[i][j]，表示从顶点 i 到顶点 j 的当前已知最短距离。

算法的核心递推公式是：

其中 k 是我们当前考虑的中间节点。通过三重循环（i、j、k），我们可以逐步优化所有顶点对之间的最短路径。

Java实现步骤

下面我们用Java一步步实现Floyd-Warshall算法。

1. 初始化距离矩阵

首先，我们需要构建一个 n×n 的距离矩阵。如果两个顶点之间没有直接边，则设为无穷大（在Java中通常用 Integer.MAX_VALUE / 2 表示，避免加法溢出）；自身到自身的距离为0。

2. 三重循环更新最短路径

外层循环遍历所有可能的中间节点 k，内层循环遍历所有起点 i 和终点 j，尝试通过 k 缩短 i 到 j 的路径。

3. 输出结果

最终，dist[i][j] 就是从 i 到 j 的最短距离。

完整Java代码示例

import java.util.Arrays;public class FloydWarshall {    private static final int INF = Integer.MAX_VALUE / 2; // 避免加法溢出    public static void floydWarshall(int[][] graph) {        int n = graph.length;        int[][] dist = new int[n][n];        // 初始化距离矩阵        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                dist[i][j] = graph[i][j];            }        }        // Floyd-Warshall 核心算法        for (int k = 0; k < n; k++) {            for (int i = 0; i < n; i++) {                for (int j = 0; j < n; j++) {                    if (dist[i][k] != INF && dist[k][j] != INF) {                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);                    }                }            }        }        // 打印结果        printSolution(dist);    }    private static void printSolution(int[][] dist) {        System.out.println("顶点之间的最短距离矩阵：");        for (int i = 0; i < dist.length; i++) {            for (int j = 0; j < dist.length; 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) {        // 示例图：4个顶点        int[][] graph = {            {0,   3,   INF, 7},            {8,   0,   2,   INF},            {5,   INF, 0,   1},            {2,   INF, INF, 0}        };        floydWarshall(graph);    }}

算法复杂度分析

• 时间复杂度：O(n³)，因为有三层嵌套循环。
• 空间复杂度：O(n²)，用于存储距离矩阵。

虽然时间复杂度较高，但Floyd-Warshall算法代码简洁，适用于顶点数量不太大的图（例如 n ≤ 500）。

适用场景与限制

适用场景：

• 需要计算所有顶点对之间的最短路径。
• 图中可能存在负权边（但不能有负权环）。

限制：

• 不能处理存在负权环的图（会导致最短路径无定义）。
• 对于稀疏图，使用 Johnson 算法或多次 Dijkstra 可能更高效。

总结

通过本教程，你已经掌握了Floyd-Warshall算法的基本原理、Java实现方法以及其适用场景。作为图论算法教程中的重要一环，该算法在路由选择、社交网络分析等领域有广泛应用。希望你能动手实践代码，加深理解！

关键词回顾：Floyd-Warshall算法、Java最短路径算法、多源最短路径、图论算法教程