如何实现Floyd最短路径算法？

Floyd 算法是一种找到图中所有节点之间的最短路径的算法。
我们可以使用邻接矩阵实现 Floyd 算法:

public int[][] 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];
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    return dist; 
}

Floyd 算法流程:

1. 构建一个二维数组 dist,初始值就是图的邻接矩阵。
2. 对中间节点 k 进行遍历。
3. 对每一对节点 (i, j) 进行遍历。
4. 更新 dist[i][j],使其等于通过 k 节点路径和不通过 k 节点路径的最小值。
5. 重复步骤 2-4,直到 k 遍历完所有节点。
6. 返回 dist 数组,即图中每个节点对之间的最短距离。

时间复杂度 O(n^3),空间复杂度 O(n^2)。

所以,Floyd 算法的关键是:

1. 构建邻接矩阵的拷贝 dist 存储每个节点对之间的最短距离。
2. 遍历中间节点 k,更新每一对节点 (i, j) 的最短距离。考虑通过 k 节点和不通过 k 节点两种情况。
3. 重复遍历中间节点,最终得到每个节点对之间的最短路径。
4. 返回 dist 数组,得到结果。