Floyd 最短路径【学习算法】

public class FloydAlgorithm {
    private static final int INF = 99999;
    public void floyd(int[][] graph, int n) {
        int[][] dist = new int[n][n];
        int i, j, k;
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
            }
        }
        for (k = 0; k < n; k++) {
            for (i = 0; i < n; i++) {
                for (j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        // 输出最短路径矩阵
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (dist[i][j] == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        //有向图
        int[][] graph = {
                {0, 5, INF, 10},
                {INF, 0, 3, INF},
                {INF, INF, 0, 1},
                {INF, INF, INF, 0}
        };
        int n = 4;
        FloydAlgorithm algorithm = new FloydAlgorithm();
        algorithm.floyd(graph, n);
    }
}