floyd算法java

Floyd算法，又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。下面是Floyd算法的Java实现：

public class FloydAlgorithm {
    private static final int INF = 999999; // 定义正无穷

    /**
     * Floyd算法实现
     * @param graph 图的邻接矩阵
     * @return 返回任意两个顶点之间的最短路径
     */
    public static int[][] floyd(int[][] graph) {
        int len = graph.length;
        int[][] dist = new int[len][len]; // 定义距离矩阵
        int i, j, k;

        // 初始化距离矩阵
        for (i = 0; i < len; i++) {
            for (j = 0; j < len; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // Floyd算法核心语句
        for (k = 0; k < len; k++) {
            for (i = 0; i < len; i++) {
                for (j = 0; j < len; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 5, INF, 6, INF},
                {INF, 0, 4, INF, INF},
                {INF, INF, 0, 3, 7},
                {INF, INF, INF, 0, 4},
                {INF, INF, INF, INF, 0}
        };

        int[][] dist = floyd(graph);

        // 输出结果
        for (int[] row : dist) {
            System.out.println(Arrays.toString(row));
        }
    }
}

以上代码中，INF表示正无穷，也就是两点之间没有路径。在初始化距离矩阵时，直接将其初始化为图的邻接矩阵。接下来，通过三重循环遍历所有路径，如果经过中间点k比直接连接更短，则更新距离矩阵。最后返回任意两个顶点之间的最短路径矩阵。