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.)

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