Problem 45 · Graphs

Network Delay Time (Dijkstra)

MediumClassic DSA & systems

01Problem

Given directed weighted edges (u, v, w) over nodes 1..n and a source k, return the time for a signal from k to reach all nodes, or -1 if some node is unreachable.

02Key insight

Dijkstra with a binary heap and lazy deletion (skip stale heap entries); the answer is the max of the shortest-path distances.

03Solution

solution.pypython18 lines

import heapq
from collections import defaultdict

def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    graph: dict[int, list[tuple[int, int]]] = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    dist: dict[int, int] = {}
    heap = [(0, k)]
    while heap:
        d, node = heapq.heappop(heap)
        if node in dist:
            continue  # stale entry
        dist[node] = d
        for nxt, w in graph[node]:
            if nxt not in dist:
                heapq.heappush(heap, (d + w, nxt))
    return max(dist.values()) if len(dist) == n else -1

Try it first.

TimeO(E log V)

SpaceO(V+E)

tests.py · 4 passing

tests.pypython4 lines

assert network_delay_time([[2,1,1],[2,3,1],[3,4,1]], 4, 2) == 2
assert network_delay_time([[1,2,1]], 2, 2) == -1
assert network_delay_time([], 1, 1) == 0
assert network_delay_time([[1,2,5],[1,3,1],[3,2,1]], 3, 1) == 2

04Staff-level follow-up

What if edge weights can be negative? Dijkstra's greedy finalization breaks; use Bellman-Ford O(VE), or Johnson's reweighting for all-pairs.