743.Network_Delay_Time(Medium).md

743. Network Delay Time (Medium)

Date and Time: Sep 25, 2024, 22:20 (EST)

Link: https://leetcode.com/problems/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] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i 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.)

Walk-through:

1. Run Dijkstra's Algorithm to find the shortest path from k to n. We use minHeap to implement this.

2. Store all src's target into edges with their weight, we can use them later.

3. Store current node's neighbors and their weights into minHeap. And for each time, we update the res = max(res, weight), and then we append this node's neighbors and weights into minHeap.

4. Finally, we return res if len(visited) == n, that means we traverse all the nodes, otherwise, we should return -1.

Python Solution:

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # Dijkstra's algorithm, maintain a minHeap [weight, node]
        # From k to all n nodes
        edges = collections.defaultdict(list)
        for u, v, w in times:
            edges[u].append((w, v))
        
        minHeap, visited = [(0, k)], set()
        res = 0
        while minHeap:
            w1, n1 = heapq.heappop(minHeap)
            if n1 not in visited:
                visited.add(n1)
                res = max(res, w1)
                # Append n1's neighbors into minHeap
                for w2, n2 in edges[n1]:
                    if n2 not in visited:
                        heapq.heappush(minHeap, (w1+w2, n2))

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

Time Complexity: $O(E * log\ V)$, E is total edges, V is total vertices. Because when we explore a new edge, we need to push a new node in minHeap, which takes $O(logV)$.
Space Complexity: $O(V)$