LC 743 - Network Delay Time

Question

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

Links

Question here and solution here

Solution

concept

This is Dijkstra’s algorithm to find the shortest path. This is basically BFS with greedy.

Compare to Prim’s algorithm in [[1584. Min Cost to Connect All Points]], take note here we add in the total distance into the heap. This distance is the total distance from starting node to that node. This is important and the difference between this and Prim’s. By doing this and keep track the maximum time used with time = max(time, weight), we can keep track the time or cost of all branches concurrently from the starting node.

We will need a min heap to keep track of the total distance from a node to a target node and every time we will process the shortest path so far and advance the frontier.

code

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        adj_list = defaultdict(list)
        for u, v, w in times:
            adj_list[u].append((v,w))
        
        min_heap = [(0, k)] # total weight, node
        visited = set()
        time = 0
        
        while min_heap:
            weight, node = heapq.heappop(min_heap)
            if node in visited:
                continue
            
            visited.add(node)
            time = max(time, weight)

            for _node, _weight in adj_list[node]:
                if _node not in visited:
                    heapq.heappush(min_heap, (weight + _weight, _node))

        return time if len(visited) == n else -1

Complexity

time: $O(E \log V)$
space: $O(E + V)$