Network Delay Time

PracticeNeetCode ↗LeetCode ↗

A network has n nodes labeled 1 to n, connected by directed edges with travel times. Starting a signal from node k, return the time for the signal to reach every node, or -1 if some node is unreachable.

Example

Key Pointers

• This is single-source shortest path with non-negative weights — Dijkstra's algorithm is the standard tool.
• The answer is the time for the signal to reach the farthest node — the maximum of all shortest distances, not their sum.
• If any node never gets a shortest distance computed, it's unreachable, so the answer is -1.

Step-by-Step Analysis

1. Build an adjacency list of (neighbor, weight) pairs from the edge list.
2. Initialize a min-heap with (0, k) and a dict recording the shortest time found for each node.
3. Pop the smallest (time, node); if that node's time is already recorded, skip it — it's a stale heap entry.
4. Otherwise record its time, then push (time + weight, neighbor) for each outgoing edge.
5. Once the heap empties, if every node 1..n has a recorded time, return the max of those times; otherwise return -1.

Complexity

Time: O(E log E) — Space: O(V + E)

Code

import heapq
from collections import defaultdict

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    shortest = {}
    min_heap = [(0, k)]

    while min_heap:
        time, node = heapq.heappop(min_heap)
        if node in shortest:
            continue
        shortest[node] = time

        for neighbor, weight in graph[node]:
            if neighbor not in shortest:
                heapq.heappush(min_heap, (time + weight, neighbor))

    if len(shortest) != n:
        return -1
    return max(shortest.values())

Code Explanation

How the solution above works, piece by piece.

1. Build an adjacency list of (neighbour, travel time).
2. The heap starts with (0, k): the signal is at the source at time 0.
3. Pop the earliest-arriving node. If it's already in shortest, a faster path got there first, so skip it. Otherwise its time is final.
4. Push each unfinished neighbour with arrival time time + weight. Non-negative weights are what make "popped first = fastest" true.
5. If some node was never reached return −1, else the answer is the latest arrival. O(E log V).

Visual Walkthrough

Running it on times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2:

Video Explanation

NeetCode — Dijkstra's Algorithm, LeetCode 743