743 Network Delay Time

1. Question

There areNnetwork nodes, labelled1toN.
Giventimes, a list of travel times as directed edgestimes[i] = (u, v, w), whereuis the source node,vis the target node, andwis the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain nodeK. How long will it take for all nodes to receive the signal? If it is impossible, return-1.
Note:
  1. 1.
    Nwill be in the range[1, 100].
  2. 2.
    Kwill be in the range[1, N].
  3. 3.
    The length oftimeswill be in the range[1, 6000].
  4. 4.
    All edgestimes[i] = (u, v, w)will have1 <= u, v <= Nand1 <= w <= 100.

2. Implementation

(1) BFS
1
class Solution {
2
public int networkDelayTime(int[][] times, int N, int K) {
3
int[][] edge = new int[N + 1][N + 1];
4
for (int[] e : edge) {
5
Arrays.fill(e, Integer.MAX_VALUE);
6
}
7
8
for (int[] time : times) {
9
edge[time[0]][time[1]] = time[2];
10
}
11
12
13
14
int[] delay = new int[N + 1];
15
Arrays.fill(delay, Integer.MAX_VALUE);
16
delay[K] = 0;
17
18
Queue<Integer> queue = new LinkedList<>();
19
queue.add(K);
20
21
while (!queue.isEmpty()) {
22
int size = queue.size();
23
Set<Integer> set = new HashSet<>();
24
25
for (int i = 0; i < size; i++) {
26
int curNode = queue.remove();
27
28
for (int nextNode = 1; nextNode <= N; nextNode++) {
29
if (edge[curNode][nextNode] != Integer.MAX_VALUE
30
&& delay[curNode] + edge[curNode][nextNode] < delay[nextNode]) {
31
if (!set.contains(nextNode)) {
32
set.add(nextNode);
33
queue.add(nextNode);
34
}
35
delay[nextNode] = delay[curNode] + edge[curNode][nextNode];
36
}
37
}
38
}
39
}
40
41
int res = 0;
42
for (int i = 1; i <= N; i++) {
43
res = Math.max(res, delay[i]);
44
}
45
return res == Integer.MAX_VALUE ? -1 : res;
46
}
47
}
Copied!
(2) Dijkstra's Algorithm
1
class Solution {
2
public int networkDelayTime(int[][] times, int N, int K) {
3
Map<Integer, List<int[]>> adjList = new HashMap<>();
4
5
for (int[] time : times) {
6
adjList.putIfAbsent(time[0], new ArrayList<int[]>());
7
adjList.get(time[0]).add(new int[] {time[1], time[2]});
8
}
9
10
int[] distance = new int[N + 1];
11
Arrays.fill(distance, Integer.MAX_VALUE);
12
13
distance[K] = 0;
14
boolean[] visited = new boolean[N + 1];
15
16
while (true) {
17
int candNode = -1;
18
int candDist = Integer.MAX_VALUE;
19
20
for (int i = 1; i <= N; i++) {
21
if (!visited[i] && distance[i] < candDist) {
22
candNode = i;
23
candDist = distance[i];
24
}
25
}
26
27
if (candNode == -1) {
28
break;
29
}
30
visited[candNode] = true;
31
32
if (adjList.containsKey(candNode)) {
33
for (int[] info : adjList.get(candNode)) {
34
int nextNode = info[0];
35
int nextDist = info[1];
36
37
distance[nextNode] = Math.min(distance[nextNode], nextDist + distance[candNode]);
38
}
39
}
40
}
41
42
int res = Integer.MIN_VALUE;
43
44
for (int i = 1; i <= N; i++) {
45
res = Math.max(res, distance[i]);
46
}
47
return res == Integer.MAX_VALUE ? -1 : res;
48
}
49
}
Copied!
(3) Dijkstra's Algorithm堆优化
1
class Solution {
2
public int networkDelayTime(int[][] times, int N, int K) {
3
Map<Integer, List<int[]>> adjList = new HashMap<>();
4
5
for (int[] time : times) {
6
adjList.putIfAbsent(time[0], new ArrayList<int[]>());
7
adjList.get(time[0]).add(new int[] {time[1], time[2]});
8
}
9
10
int[] distance = new int[N + 1];
11
Arrays.fill(distance, Integer.MAX_VALUE);
12
13
PriorityQueue<int[]> minHeap = new PriorityQueue<int[]>((info1, info2) -> (info1[1] - info2[1]));
14
minHeap.add(new int[] {K, 0});
15
16
while (!minHeap.isEmpty()) {
17
int[] info = minHeap.remove();
18
int curNode = info[0];
19
int curDist = info[1];
20
21
// 最小堆每次都会pop出最小距离的node,如果distance[node]不等于 Integer.MAX_VALUE,说明该node的距起点的最小距离已经更新,所以不再更新
22
if (distance[curNode] != Integer.MAX_VALUE) {
23
continue;
24
}
25
26
distance[curNode] = curDist;
27
if (adjList.containsKey(curNode)) {
28
for (int[] nextInfo : adjList.get(curNode)) {
29
int nextNode = nextInfo[0];
30
int nextDist = nextInfo[1];
31
32
if (distance[nextNode] == Integer.MAX_VALUE) {
33
minHeap.add(new int[] {nextNode, curDist + nextDist});
34
}
35
}
36
}
37
}
38
39
int res = Integer.MIN_VALUE;
40
for (int i = 1; i <= N; i++) {
41
res = Math.max(res, distance[i]);
42
}
43
return res == Integer.MAX_VALUE ? -1 : res;
44
}
45
}
Copied!

3. Time & Space Complexity

BFS: 时间复杂度O(N ^ 2), 空间复杂度O(N ^ 2)
Dijkstra's Algorithm: 时间复杂度O(N ^ 2 + E), E是times的长度,空间复杂度O(N + E)
Dijkstra's Algorithm堆优化: 时间复杂度O(NlogN + E), 空间复杂度O(N + E)