最短路径之Dijkstra算法

1import java.util.Arrays;
2import java.util.PriorityQueue;
3
4public class Main {
5
6    private static final int INF = Integer.MAX_VALUE;
7
8    public static void main(String[] args) {
9        int[][] map = new int[][]{
10                {0, 1, 12, INF, INF, INF},
11                {INF, 0, 9, 3, INF, INF},
12                {INF, INF, 0, INF, 5, INF},
13                {INF, INF, 4, 0, 13, 15},
14                {INF, INF, INF, INF, 0, 4},
15                {INF, INF, INF, INF, INF, 0}
16        };
17        System.out.println(Arrays.toString(dijkstra(map)));
18        System.out.println(Arrays.toString(dijkstraUsingPQ(map)));
19    }
20
21    /**
22     * dijkstra 算法求最短路径
23     *
24     * @param map 图，邻接矩阵表示
25     * @return 起点到所有点的最短距离
26     */
27    public static int[] dijkstra(int[][] map) {
28        /**
29         * 记录顶点是否访问
30         */
31        boolean[] visited = new boolean[map.length];
32        /**
33         * 记录所有顶点到起始点的最短距离
34         */
35        int[] distance = new int[map.length];
36        /**
37         * 除一个起始点以外，其它顶点距离初始化为∞
38         */
39        for (int i = 1; i < distance.length; i++) {
40            distance[i] = INF;
41        }
42        for (int i = 0; i < map.length; i++) {
43            int min = INF, vertex = -1;
44            /**
45             * 选择当前未访问过的且距离起始点最近的顶点
46             */
47            for (int j = 0; j < map.length; j++) {
48                if (!visited[j] && distance[j] < min) {
49                    min = distance[j];
50                    vertex = j;
51                }
52            }
53            visited[vertex] = true;
54            /**
55             * 更新所有可以以上面选择的顶点作为中转点的其它顶点
56             */
57            for (int j = 0; j < map.length; j++) {
58                if (visited[j] || map[vertex][j] == INF
59                        || distance[vertex] + map[vertex][j] >= distance[j]) {
60                    continue;
61                }
62                distance[j] = distance[vertex] + map[vertex][j];
63            }
64        }
65        return distance;
66    }
67
68    /**
69     * dijkstra 算法求最短路径
70     * 使用优先队列，可以不用每次遍历寻找当前未访问过的且距离起始点最近的顶点
71     *
72     * @param map 图，邻接矩阵表示
73     * @return 起点到所有点的最短距离
74     */
75    public static int[] dijkstraUsingPQ(int[][] map) {
76        /**
77         * 记录顶点是否访问
78         */
79        boolean[] visited = new boolean[map.length];
80        int[] distance = new int[map.length];
81        /**
82         * 除一个起始点以外，其它顶点距离初始化为∞
83         */
84        for (int i = 1; i < distance.length; i++) {
85            distance[i] = INF;
86        }
87        PriorityQueue<Node> queue = new PriorityQueue<>();
88        queue.offer(new Node(0, distance[0]));
89        while (!queue.isEmpty()) {
90            /**
91             * 获取当前未访问过的且距离起始点最近的顶点
92             */
93            Node node = queue.poll();
94            if (visited[node.vertex]) {
95                continue;
96            }
97            visited[node.vertex] = true;
98            /**
99             * 更新所有可以以上面选择的顶点作为中转点的其它顶点
100             */
101            for (int i = 0; i < map.length; i++) {
102                if (visited[i] || map[node.vertex][i] == INF
103                        || node.distance + map[node.vertex][i] >= distance[i]) {
104                    continue;
105                }
106                distance[i] = node.distance + map[node.vertex][i];
107                queue.offer(new Node(i, distance[i]));
108            }
109        }
110        return distance;
111    }
112}
113
114class Node implements Comparable<Node> {
115
116    int vertex;
117    int distance;
118
119    public Node(int vertex, int distance) {
120        this.distance = distance;
121        this.vertex = vertex;
122    }
123
124    @Override
125    public int compareTo(Node o) {
126        return distance - o.distance;
127    }
128}
129