Problem Statement in English

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.

Your task is to send a signal from a given node k and return the 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.

Approach

So the main thing to keep in mind here is that we always choose the quickest time that a signal reaches each node. Even if the signal reaches a node later through another path, we don’t consider that path since we are only interested in the quickest time.

So this brings us to Dijkstra’s algorithm, which is perfect for finding the shortest path in a weighted graph with non-negative weights.

We start from the given node k and explore all its neighbors, updating the time it takes to reach each neighbor if we find a quicker path. We use a min-heap (priority queue) to always expand the least time-consuming path first.

Solution in Python


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        seen = set()

        adj = defaultdict(list)

        for u, v, t in times:
            adj[u].append((t, v))

        minheap = [(0, k)]
        res = -inf

        while minheap:
            t, node = heappop(minheap)
            
            if node in seen:
                continue
            
            res = max(res, t)
            seen.add(node)

            for time, nn in adj[node]:
                if nn not in seen:
                    heappush(minheap, (t + time, nn))

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

Complexity

  • Time: $O((V + E) \log V)$
    Where V is the number of vertices (nodes) and E is the number of edges (times). This is because we potentially visit each node and edge once, and each operation on the min-heap takes logarithmic time.

  • Space: $O(V + E)$
    We use space to store the adjacency list and the min-heap, which in the worst case can hold all vertices and edges.

And we are done.