Dijkstra算法

算法的思想就是从起点开始,找到和起点连通的还最小距离的点,选中该点,到达该点的最短路径也就找到了,然后根据这点作为中介点,去找有没有起始点到中介点+中介点到下一点的距离小于起始点到下一点,有的话就更新新点到起始点的距离.然后回到开始,循环这个过程,就可以找到起始点到所有点的最短路径

public class DijkstraTest {
    static int M = 10000;//不能用Integer的最大值代替,数值会越界

    public static void main(String[] args) {
        int[][] times = new int[][]{
                {0, 4, M, 2, M},
                {4, 0, 4, 1, M},
                {M, 4, 0, 1, 3},
                {2, 1, 1, 0, 7},
                {M, M, 3, 7, 0}
        };
        int start = 0;
        int[] resultPath = dijkstra(times, start);
        for (int i = 1; i < resultPath.length; i++) {
            System.out.println("The min distance form " + start + " to "+i+" is " + resultPath[i]);
        }
    }

    private static int[] dijkstra(int times[][], int start) {
        int n = times.length;
        int[] visited = new int[n];
        int[] resultpath = new int[n];
        String[] pathtrace = new String[n];
        for (int i=0;i<n;i++) {
            pathtrace[i] = start+"->"+i;
        }
        resultpath[start] =0;
        visited[start]=1;

        for (int count = 1; count < n; count++) {//要添加n-1个点
            int min = Integer.MAX_VALUE;
            int mini = -1;
            for (int i = 0; i < n; i++) {
                if (visited[i] == 0 && times[start][i] < min) {
                    min = times[start][i];
                    mini = i;
                }
            }
            resultpath[mini] = min;
            visited[mini] = 1;

            for (int i=0;i<n;i++){
                if (visited[i]==0&&times[start][mini]+times[mini][i]<times[start][i]){
                    times[start][i] = times[start][mini]+times[mini][i];
                    pathtrace[i] = pathtrace[mini] +"->" +i;
                }
            }
        }
        for (int i = 1; i < n; i++) {
            System.out.println("The shortest path form " + start + " to " + i +" is "+ pathtrace[i]);
        }
        return resultpath;
    }
}

输出:
The shortest path form 0 to 1 is 0->3->1
The shortest path form 0 to 2 is 0->3->2
The shortest path form 0 to 3 is 0->3
The shortest path form 0 to 4 is 0->3->2->4
The min distance form 0 to 1 is 3
The min distance form 0 to 2 is 3
The min distance form 0 to 3 is 2
The min distance form 0 to 4 is 6