time O(E log V)
space O(V + E)
1
2
3
4
Initialize graph. Source node is 2. Distances to all nodes are Infinity, except dist[2] = 0.
Pseudocode
Pseudocode
1function networkDelayTime(times, n, k):
2 graph = buildAdjacencyList(times)
3 dist = array of infinity, dist[k] = 0
4 pq = [(0, k)] // (distance, node)
5 while pq is not empty:
6 (d, u) = pq.popMin()
7 if d > dist[u]: continue
8 for (v, w) in graph[u]:
9 if dist[u] + w < dist[v]:
10 dist[v] = dist[u] + w
11 pq.push((dist[v], v))
12 maxDist = max(dist)
13 return maxDist == infinity ? -1 : maxDist