LeetCode Network Delay Time Solution
You are given a network of n
nodes, labeled from 1
to n
. You are also given times
, a list of travel times as directed edges times[i] = (ui, vi, wi)
, where ui
is the source node, vi
is the target node, and wi
is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k
. Return the minimum time it takes for all the n
nodes to receive the signal. If it is impossible for all the n
nodes to receive the signal, return -1
.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Example 2:
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Example 3:
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Constraints:
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
- All the pairs
(ui, vi)
are unique. (i.e., no multiple edges.)
Problem Link: https://leetcode.com/problems/network-delay-time/
Solution
We wish to find the shortest path from k
to all nodes in the graph.
Dijkstra's algorithm is the best approach in finding shortest path from a single source.
We will keep track of the delay time from k
to each node, and find the maximum in the end.
Implementation
1def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
2 graph = defaultdict(list)
3 for src, dst, time in times:
4 graph[src].append((time, dst))
5
6 queue = [(0, k)]
7 delay_time = [inf for _ in range(n+1)]
8 while queue:
9 cur_time, cur_node = heapq.heappop(queue) # pop min from min-heap
10 if cur_time > delay_time[cur_node]: # a shorter path exists
11 continue
12 for edge in graph[cur_node]:
13 new_time, new_node = edge
14 if delay_time[new_node] > cur_time + new_time:
15 delay_time[new_node] = cur_time + new_time
16 heapq.heappush(queue, (delay_time[new_node], new_node))
17
18 max_delay = max(delay_time)
19 return max_delay if max_delay != inf else -1