最短路径算法

ShortestPathOfDijkstra

package graph.dijkstra;

import java.util.Arrays;

/**
 * description
 * 狄克斯特拉算法的时间复杂度O(n^2)
 * https://blog.csdn.net/shui2104/article/details/107053966
 * https://www.bbsmax.com/A/qVde9lOrdP/
 *
 * @author liekkas 2021/08/22 16:14
 */
public class ShortestPathOfDijkstra {
    private static final int MAX = 10000;

    /**
     * 接受一个有向图的权重矩阵，和一个起点编号start（从0编号，顶点存在数组中)
     *
     * @param graph           graph
     * @param startPointIndex startPointIndex
     * @return 返回一个int[] 数组，表示从start到它的最短路径长度
     */
    public static int[] dijsktra(int[][] graph, int startPointIndex) {
        int length = graph.length;
        //标记当前该顶点的最短路径是否已经求出，true表示已经求出
        boolean[] visited = new boolean[length];
        //start点的最短距离已经求出
        for (int i = 0; i < graph.length; i++) {//初始化s集合，只有起始点
            if (i == startPointIndex) {
                visited[i] = true;
            } else {
                visited[i] = false;
            }
        }

        //存放从start到各个点的最短距离
        int[] shortDistance = new int[length];

        for (int i = 0; i < graph.length; i++) {//初始化，起始点到其他点的距离。
            shortDistance[i] = graph[startPointIndex][i];
        }

        //start到他本身的距离最短为0
        shortDistance[startPointIndex] = 0;


        //存放从start点到各点的最短路径的字符串表示
        String[] path = new String[length];
        for (int i = 0; i < length; i++) {
            path[i] = startPointIndex + "->" + i;
        }


        for (int count = 1; count < length; count++) {
            int k = -1;
            int dmin = MAX;
            for (int i = 0; i < length; i++) {
                if (!visited[i] && shortDistance[i] < dmin) {
                    dmin = shortDistance[i];
                    k = i;
                }
            }
            //选出一个距离start最近的未标记的顶点     将新选出的顶点标记为以求出最短路径，且到start的最短路径为dmin。
            shortDistance[k] = dmin;
            visited[k] = true;
            //以k为中间点，修正从start到未访问各点的距离
            for (int i = 0; i < length; i++) {
                if (!visited[i] && shortDistance[k] + graph[k][i] < shortDistance[i]) {
                    shortDistance[i] = shortDistance[k] + graph[k][i];
                    path[i] = path[k] + "->" + i;
                }
            }
        }
        for (int i = 0; i < length; i++) {
            System.out.println("从" + startPointIndex + "出发到" + i + "的最短路径为：" + path[i] + "=" + shortDistance[i]);
        }
        return shortDistance;
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 4, 6, 6, MAX, MAX, MAX},
                {MAX, 0, 1, MAX, 7, MAX, MAX},
                {MAX, MAX, 0, MAX, 6, 4, MAX},
                {MAX, MAX, 2, 0, MAX, 5, MAX},
                {MAX, MAX, MAX, MAX, 0, MAX, 6},
                {MAX, MAX, MAX, MAX, 1, 0, 8},
                {MAX, MAX, MAX, MAX, MAX, MAX, MAX}};
        int start = 0;
        int[] dijsktra = dijsktra(graph, start);
        System.out.println(Arrays.toString(dijsktra));
    }
}

ShortestPathOfFloyd

package graph.floyd;

/**
 * description floyd最短路径
 * 时间复杂度O(V*E) 空间复杂度O(V^2)
 * https://blog.csdn.net/qq_34842671/article/details/90637502
 *
 * @author liekkas 2021/08/22 13:35
 */
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;
                    }
                }
            }
            print(MATRIX);
        }


/*        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (i != j) {
                    if (matrix[i][j] == MAX_VALUE) {
                        System.out.println(i + "到" + j + "不可达");
                    } else {
                        System.out.print(i + "到" + j + "的最短路径长度是：" + matrix[i][j]);
                        System.out.print("最短路径为：" + i + "->");
                        findPath(i, j);
                        System.out.println(j);
                    }
                }
            }
        }*/


        int i = 0, j = 5;
        if (matrix[i][j] == MAX_VALUE) {
            System.out.println(i + "到" + j + "不可达");
        } else {
            System.out.print(i + "到" + j + "的最短路径长度是：" + matrix[i][j]);
            System.out.print("最短路径为：" + i + "->");
            findPath(i, j);
            System.out.println(j);
        }


    }

    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);
    }

    static void print(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                System.out.printf("%-10d", a[i][j]);
                if (j != a[i].length - 1) {
                    System.out.print(",");
                }
            }
            System.out.println();
        }
    }
}