1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| class Program {
public int[] dijkstrasAlgorithm(int start, int[][][] edges) {
int numberOfVertex = edges.length;
int[] minDistances = new int[numberOfVertex];
Arrays.fill(minDistances, Integer.MAX_VALUE);
minDistances[start] = 0;
Set<Integer> visited = new HashSet<Integer>();
while (visited.size() != numberOfVertex) {
int[] currentVertexData = getVertexWithMinDistances(minDistances, visited);
int currentVertexIdx = currentVertexData[0];
int currentVertexDistanceToStart = currentVertexData[1];
if (currentVertexDistanceToStart == Integer.MAX_VALUE) {
break;
}
visited.add(currentVertexIdx);
for (int[] edge : edges[currentVertexIdx]) {
int destination = edge[0];
int distanceToDestination = edge[1];
if (visited.contains(destination)) {
continue;
}
int newPathToDestinationDistance = currentVertexDistanceToStart + distanceToDestination;
if (newPathToDestinationDistance < minDistances[destination]) {
minDistances[destination] = newPathToDestinationDistance;
}
}
}
int[] finalDistances = new int[numberOfVertex];
for (int i = 0; i < numberOfVertex; i++) {
finalDistances[i] = minDistances[i] == Integer.MAX_VALUE ? -1 : minDistances[i];
}
return finalDistances;
}
public int[] getVertexWithMinDistances(int[] minDistances, Set<Integer> visited) {
int vertex = -1;
int currentMinDistance = Integer.MAX_VALUE;
for (int vertexIdx = 0; vertexIdx < minDistances.length; vertexIdx++) {
if (visited.contains(vertexIdx)) {
continue;
}
int currentDistance = minDistances[vertexIdx];
if (currentDistance <= currentMinDistance) {
vertex = vertexIdx;
currentMinDistance = currentDistance;
}
}
return new int[] { vertex, currentMinDistance };
}
}
|
AlgoExpert的写法. 大致思路就是我们用一个数组叫做min来记录到每个node的最短距离是多少. 一开始把这个数组初始化为Integer.MAX_VALUE. 因为可能有些node到达不了. 然后我们把start在min中的位置标记为0, 表示到start所需要的距离是0. 然后从这个node开始, 看start周围的neighbor, 到它们的距离是多少, 然后更新这个min, 把neighbors在min中的位置的内容都更新一下. 当我们把neighbors都遍历完后, 我们看看现在min中去下一个node哪个最近, 由于此时min中肯定是start最小, 是0, 因此我们用一个visited的set来存去过的node. 我们去到除了start外最近的node. 然后看它的neighbor, 此时start肯定是它的neighbor, 但是visited过了, 这说明到start的距离不可能更短了, 于是这一步visited的跳过. 我们会遇到有的neighor同样也是start的neighbor, 那是从这里到那个neighbor更近还是从start更近呢? 看一下比较一下就行了, 如果这里更近, 那就更新一下min即可. 然后我们再看min中没去过的node中最近的是哪一个. 这里的近指的是从start出发到哪个node更近. 重复上面的过程, 直到visit完所有的node, 或者发现min中没有被visite的node中最小的距离是Integer.MAX_VALUE, 这说明这个node不能到达, 其他有这个值的node也不能到达. 此时就可以brek了.
此时可以总结一下, 这个算法是按照距离start由近到远的距离去visit nodes. 在visit一个node的时候, 我们更新该node的neighbors在min中的信息. 被之前visited的neighbor不需要更新, 因为到达当前node前, 这个neighbor就已经被visited过, 这说明从start到该neighor更近, 如果在这里去neighbor, 首先我们要到这里, 此时距离已经比直接从start到neighbor要远, 更别说还要从这里到neighbor, 又有距离, 因此被visited过的neighbor不需要更新. 每次visit下一个node的时候, 找min中没被visit过的nodes中距离start最近的去visit. 如果此时未被visited过的node的最短距离是Intger.MAX_VALUE, 这表示这个node不能被到达. 其他有同样值的node也不能被到达. 最后我们根据min的信息来生成finalDistance.
Min Heap(PQ)做法
还有用min heap的做法, 具体见LC 743题. 简单来说就是把neighbor都装到min heap里面, 到我们要visit一个node的时候, 如果visit过, 直接continue, 这说明之前有更近的路线到达过这个node. 我们此时到达的路线太远, 直接忽略.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
for (int[] time : times) {
int from = time[0], to = time[1], dist = time[2];
graph.computeIfAbsent(from, k -> new HashMap<>()).put(to, dist);
}
Queue<int[]> que = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
Set<Integer> visited = new HashSet<>();
que.offer(new int[]{K, 0});
int count = 0, res = 0;
while (!que.isEmpty()) {
int[] cur = que.poll();
int node = cur[0], dist = cur[1];
if (visited.contains(node)) { continue; }
count++;
res = dist;
if (count == N) break;
visited.add(node);
if (!graph.containsKey(node)) { continue; }
for (Map.Entry<Integer, Integer> next : graph.get(node).entrySet()) {
if (visited.contains(next.getKey())) continue;
que.offer(new int[]{next.getKey(), next.getValue() + dist});
}
}
return count == N ? res : -1;
}
}
|
这个是模板.
