图最短路径之Floyd

public class ShortestPathOfFloyd {
    private final static int VERTEX = 7;
    private final static int[][] MATRIX = new int[VERTEX][VERTEX];
    private final static int[][] PATH = new int[MATRIX.length][MATRIX.length];
    private final static int MAX_VALUE = 100000;
?
    /**
     * 初始化邻接矩阵
     */
    static void initMatrix() {
        for (int i = 0; i < VERTEX; i++) {
            for (int j = 0; j < VERTEX; j++) {
                MATRIX[i][j] = MAX_VALUE;
            }
        }
    }
?
    /**
     * 初始化边
     */
    static void initEdge() {
        MATRIX[0][1] = 6;
        MATRIX[0][3] = 2;
        MATRIX[1][2] = 5;
        MATRIX[1][5] = 3;
        MATRIX[3][4] = 5;
        MATRIX[3][1] = 7;
        MATRIX[4][6] = 1;
        MATRIX[5][4] = 2;
        MATRIX[5][2] = 3;
    }
?
    public static void main(String[] args) {
        initMatrix();
        initEdge();
        //调用算法计算最短路径
        floyd(MATRIX);
    }
?
    @SuppressWarnings("all")
    private static void floyd(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                PATH[i][j] = -1;
            }
        }
        for (int m = 0; m < matrix.length; m++) {
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    if (matrix[i][m] + matrix[m][j] < matrix[i][j]) {
                        matrix[i][j] = matrix[i][m] + matrix[m][j];
                        //记录经由哪个点到达
                        PATH[i][j] = m;
                    }
                }
            }
        }
?
        for (int i = 0; i < matrix.length; i++) {
            getPath(matrix, 0, i);
        }
?
?
    }
?
    private static void getPath(int[][] matrix, int start, int destination) {
?
        if (matrix[start][destination] == MAX_VALUE) {
            System.out.println(start + "到" + destination + "不可达");
        } else {
            System.out.print(start + "到" + destination + "的最短路径长度是：" + matrix[start][destination]);
            System.out.print("最短路径为：" + start + "->");
            findPath(start, destination);
            System.out.println(destination);
        }
    }
?
    private static void findPath(int i, int j) {
        int m = PATH[i][j];
        if (m == -1) {
            return;
        }
        findPath(i, m);
        System.out.print(m + "->");
        findPath(m, j);
    }
?
}
?

版权声明：本文为CSDN博主「廿半」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_34842671/article/details/90637502

图最短路径之Floyd

原文：https://www.cnblogs.com/wkynf/p/15202728.html