LeetCode #743 Medium

Network Delay Time

Compute when all nodes receive a signal sent from one node through weighted directed edges.

graphdijkstrashortest-path

02

Intuition

Taking the fewest edges does not minimize travel time when weights differ. Each node receives the signal at its shortest-path distance from the source, which Dijkstra calculates for nonnegative weights. Processing the closest unsettled node makes its distance final. The network delay is the largest finalized distance, unless some node is unreachable.

How to spot this pattern

Single-source minimum arrival times with nonnegative weighted edges point directly to Dijkstra's algorithm. A request for the time until everyone is reached asks for the maximum finite shortest-path distance.

03

Approach

1

Build directed weighted adjacency lists

For every triple (u, v, w), store (v, w) under u. Direction matters because a signal may travel from u to v without a reverse route.

2

Finalize arrival times with a min-heap

Start the heap at (0, k). Skip a popped node if it was already finalized; otherwise record its cost and push every outgoing neighbor with accumulated travel time.

3

Measure the last receiver

If exactly n nodes were finalized, the maximum recorded distance is when the last node receives the signal. If fewer were reached, return -1 to report disconnection.

04

Solution

▶1class Solution:
▶2    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
▶3        graph = defaultdict(list)
▶4        for source, destination, weight in times:
▶5            graph[source].append((destination, weight))
▶6 
▶7        heap = [(0, k)]
▶8        distance = {}
▶9        while heap:
▶10            cost, node = heappop(heap)
▶11            if node in distance:
▶12                continue
▶13            distance[node] = cost
▶14            for neighbor, weight in graph[node]:
▶15                if neighbor not in distance:
▶16                    heappush(heap, (cost + weight, neighbor))
▶17 
▶18        return max(distance.values()) if len(distance) == n else -1

05

Common pitfalls

Treating edges as undirected

✗ Wrong

graph[v].append((u, w))

✓ Right

graph[u].append((v, w))

The listed travel time applies only in the given direction.

Using edge count instead of weight

✗ Wrong

heappush(heap, (cost + 1, neighbor))

✓ Right

heappush(heap, (cost + weight, neighbor))

Arrival time accumulates the provided edge weights.

Returning a maximum for a disconnected graph

✗ Wrong

return max(distance.values())

✓ Right

return max(distance.values()) if len(distance) == n else -1

Missing nodes mean the signal never reaches the entire network.

06

Edge cases

The source is the only node

Its distance is zero, so the delay is zero.

Parallel edges have different weights

Both candidates may enter the heap, and the lower arrival is finalized first.

A node has no route from the source

It never becomes finalized, so return -1.

07

Complexity

Time

O((V + E) log V)

Space

O(V + E)

Adjacency storage and the shortest-path frontier dominate memory.