java实现Floyd算法

Java实现Floyd算法

Floyd算法是解决图中最短路问题的一种经典算法，它可以求出图中任意两点之间的最短路径。下面我们将详细讲解如何使用Java实现Floyd算法。

算法思路

Floyd算法是一种动态规划算法，它通过逐步优化不同的路径来求取图中任意两点之间的最短路径。

我们可以用一个二维数组dis来存储图中任意两点之间的距离。具体地，dis[i][j]表示从顶点i到顶点j的最短距离，如果i和j之间没有边相连，则dis[i][j]为正无穷大。初始时，dis[i][j]的值为相邻顶点之间的距离，如果相邻顶点之间没有边相连，则值为正无穷大。接下来，我们将遍历整个二维数组，并尝试以当前顶点为中转点来缩短从i到j之间的距离。具体地，如果从i到j经过顶点k可以缩短距离，我们就更新dis[i][j]的值为dis[i][k]+dis[k][j]。

代码实现

下面是Floyd算法的Java实现代码，假设我们已经用一个二维数组adj来存储图的邻接矩阵。

public static void floyd(int[][] adj, int n) {
    int[][] dis = new int[n][n];
    // 初始化dis数组
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dis[i][j] = adj[i][j];
        }
    }
    // 更新dis数组
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dis[i][k] != Integer.MAX_VALUE && dis[k][j] != Integer.MAX_VALUE) {
                    dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
    }
    // 打印结果
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.print(dis[i][j] + " ");
        }
        System.out.println();
    }
}

示例说明

假设我们有一个包含5个顶点的图，其邻接矩阵为：

0 1 3 ∞ ∞
∞ 0 1 5 ∞
∞ ∞ 0 2 ∞
∞ ∞ ∞ 0 4
2 ∞ ∞ ∞ 0

我们调用floyd(adj, 5)，会得到以下输出：

0 1 3 6 10
∞ 0 1 5 9
∞ ∞ 0 2 6
∞ ∞ ∞ 0 4
2 3 5 8 0

输出的结果表示图中任意两点之间的最短路径长度。例如，从顶点1到顶点4的最短路径长度为5，从顶点5到顶点2的最短路径长度为3。