Network Delay Time

Network Delay Time is a clean, classic application of Dijkstra's algorithm — the standard tool for shortest paths on a graph with non-negative edge weights. If you can trace Dijkstra, you can solve a large family of "fastest / cheapest path" interview problems.

The slow way first

You could try every possible path from the source to every node and keep the shortest — but the number of paths explodes, so that is hopelessly slow. Even repeatedly scanning all nodes to find the next closest one (plain Dijkstra without a heap) costs O(n²), which is fine for tiny graphs but wasteful.

The real question: given the distances I know so far, which node is definitely finished? The answer is always the closest unfinalized node — nothing shorter can reach it later. A min-heap hands us that node instantly.

The idea: always expand the closest node

Keep a dist map (best-known time to each node) and a min-heap of (distance, node) pairs. Repeatedly pop the smallest. That node is now finalized — its distance can never improve. Relax each outgoing edge: if going through this node gives a shorter distance to a neighbor, update it and push the new pair. When the heap is empty, every reachable node holds its true shortest distance.

The answer is the maximum finalized distance: the signal has reached everyone only once the slowest node has heard it. If any node is still missing from dist at the end, it was unreachable, so we return -1.

Walk through it

Step through the animation. The source node 1 lights up first. Each pop finalizes the closest node (turning it green) and relaxes its edges, lowering distances in the panel on the right. Watch dist[3] drop from 4 to 3 and dist[4] drop from 9 to 5 as shorter routes appear. A stale heap entry — (4, 3) after node 3 was already finalized at 3 — gets popped and skipped. The last node to finalize is node 5 at distance 8, which is the answer.

Pseudocode

build adjacency list: node -> list of (neighbor, weight)
dist = { source: 0 }
heap = [ (0, source) ]
while heap is not empty:
    (d, u) = pop smallest from heap
    if d > dist[u]:            # a stale, outdated entry
        skip it
    for each (v, w) in neighbors of u:
        nd = d + w
        if nd < dist[v]:        # found a shorter route to v
            dist[v] = nd
            push (nd, v) onto heap
if some node never got a distance:
    return -1
return the largest value in dist

The Python solution

def network_delay_time(times, n, k):
    graph = build_adjacency(times)
    dist = {k: 0}
    heap = [(0, k)]
    while heap:
        d, u = heappop(heap)
        if d > dist.get(u, inf):
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, inf):
                dist[v] = nd
                heappush(heap, (nd, v))
    if len(dist) < n:
        return -1
    return max(dist.values())

• graph maps each node to its list of (neighbor, weight) edges.
• dist holds the best-known distance; the source starts at 0 and is the only known node.
• The heap is ordered by distance, so heappop always returns the closest unfinalized node.
• Line 6 pops that node. The d > dist.get(u, inf) check skips stale entries — an old, larger distance we already improved on.
• Lines 11-13 are the relaxation: if d + w beats the neighbor's current distance, record it and push the new pair.
• At the end, an unreachable node is simply absent from dist, so len(dist) < n means return -1; otherwise the answer is the largest distance.

Complexity

With a min-heap, each edge causes at most one push, and every heap operation is O(log V), giving O(E log V) — the standard bound for Dijkstra on a sparse graph.

When this pattern shows up

Practice