LeetCode Network Delay Time Solution
You are given a network of
n nodes, labeled from
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
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
times = [[1,2,1]], n = 2, k = 1
times = [[1,2,1]], n = 2, k = 2
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/
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.
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