743. Network Delay Time

Medium

Problem:

Calculate the time it takes for all nodes to receive a signal starting from node $k$. If it's impossible, return -1. The input values (u, v, w) represent the starting point, destination, and time taken respectively. The total number of nodes is given as $n$.

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

https://leetcode.com/problems/network-delay-time/

Solution:

In this problem, two things need to be determined:

1. The time it takes for every node to receive the signal - this is the time taken to reach the node that takes the longest.

2. Whether all nodes can be reached - This can be determined by checking if the Dijkstra's algorithm value exists for all nodes.

In the pseudocode, functions like add_with_priority(), decrease_priority(), and extract_min() are used. However, the actual Python heapq module does not support the decrease_priority() function to update priorities. (To update a priority, first we need to find the corresponding key, which ultimately takes $O(n)$ time.)

Therefore, rather than updating the queue's priority, it can ensure that dist always sets the minimum value by checking the inclusion of a node in dist.

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        print(graph)
        # Queue: [(time, node)]
        q = [(0, k)]
        dist = collections.defaultdict(int)

        # Insert the shortest path into priority queue
        while q:
            time, node = heapq.heappop(q)
            if node in dist:
                continue
            dist[node] = time

            for v, w in graph[node]:
                alt = time + w
                heapq.heappush(q, (alt, v))

        # Check if every node has the shortest path
        if len(dist) == n:
            return max(dist.values())

        return -1

Reference: https://www.youtube.com/watch?v=EaphyqKU4PQ

Time complexity: $O(E\times{logV})$