Network Delay Time

Once edges carry weights, BFS stops being correct. It counts edges, not cost. Take three nodes: A to C costs 5, while A to B and B to C cost 1 each. BFS reaches C in one hop and reports 5, but A → B → C costs 2. Dijkstra's algorithm is the repair: expand nodes in order of total cost, not in order of hops.

The problem

A network has n nodes, numbered 1 to n. You are given directed edges [u, v, t]: a signal sent from u reaches v after t time units. A signal starts at node k. Return the time until every node has received it. If some node never receives it, return -1.

Example 1. n = 4, k = 1, edges [[1, 2, 1], [1, 3, 4], [2, 3, 2], [2, 4, 6], [3, 4, 3]] → 6. The fastest times are: node 2 at 1; node 3 at 3 (via 2, cheaper than the direct 4); node 4 at 6 (via 2 and 3, cheaper than 1 + 6 = 7). The last node hears the signal at time 6.

Example 2. n = 3, k = 1, edges [[1, 2, 5]] → -1. Node 3 has no incoming edge.

Constraints. Up to 10^4 nodes and 10^5 edges. Times are integers from 0 to 100.

Clarifying questions

• Directed? Yes: u → v does not imply v → u.
• Can times be negative? No — this decides the algorithm, so always ask.
• Can there be several edges between the same pair? Assume not; the solution handles it anyway.
• Is the answer "all nodes heard it"? Yes: the maximum of all shortest times.

Approach 1: the simple way — Bellman-Ford

The reframe comes first: "when does the last node hear it?" is "the largest of all the shortest times". Now compute shortest times the simplest way. Start with 0 at k and infinity elsewhere. Go through every edge and relax it: if reaching u and then taking u → v is faster than v's current time, lower v's time. Repeat the pass. A shortest path uses at most n − 1 edges, and pass i fixes every shortest path of i edges, so n − 1 passes are enough.

1def network_delay_bellman_ford(times: list[list[int]], n: int, k: int) -> int:2    """Relax every edge up to n-1 times."""3    dist = [float("inf")] * (n + 1)4    dist[k] = 05    for _ in range(n - 1):6        changed = False7        for u, v, w in times:8            if dist[u] + w < dist[v]:9                dist[v] = dist[u] + w10                changed = True11        if not changed:12            break                                # nothing moved: already final13    longest = max(dist[1:])14    return -1 if longest == float("inf") else int(longest)

On Example 1 the edges happen to be listed in a helpful order, so pass 1 already gives [0, 1, 3, 6] and pass 2 changes nothing and stops. In the worst case, though, it needs all n − 1 passes over all E edges: O(V × E). With 10^4 nodes and 10^5 edges that is 10^9 relaxations. The waste: every pass re-relaxes edges out of nodes whose times are already final.

The key insight

Process nodes in order of their time, smallest first. When the node with the smallest known time is taken, its time is final. Any other route to it must pass through some node that is not yet final, whose time is already at least as large — and since no edge has a negative time, continuing from there can only add. So each node needs to be expanded once, at the moment it is the closest unfinished node.

Finding "the smallest known time" quickly is a job for a min-heap. That is Dijkstra's algorithm: BFS with the queue replaced by a priority queue keyed by total time.

The whole argument rests on one condition: no negative edges. Say it out loud before you write the code.

Approach 2: Dijkstra

1import heapq234def network_delay_time(times: list[list[int]], n: int, k: int) -> int:5    """Dijkstra from k; the answer is the largest shortest distance."""6    graph: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]7    for u, v, w in times:8        graph[u].append((v, w))9    dist = [float("inf")] * (n + 1)10    dist[k] = 011    heap = [(0, k)]                              # (distance so far, node)12    while heap:13        d, u = heapq.heappop(heap)14        if d > dist[u]:15            continue                             # stale entry: u already settled16        for v, w in graph[u]:17            if d + w < dist[v]:                  # relax the edge18                dist[v] = d + w19                heapq.heappush(heap, (dist[v], v))20    longest = max(dist[1:])21    return -1 if longest == float("inf") else int(longest)

Step by step:

1. Build an adjacency list of (neighbour, time) pairs.
2. Push (0, k). Pop the smallest entry each time.
3. Skip stale entries. Python's heapq cannot lower a key in place, so when a node's time improves, a new entry is pushed and the old one stays behind. When an old entry is popped later, its time is larger than dist[u]; skip it.
4. Relax each outgoing edge; if a time improves, record it and push the new entry.
5. The answer is the largest time among nodes 1 to n, or -1 if any is still infinite.

Dry run on Example 1. The heap is shown sorted.

Final times: 0, 1, 3, 6. The largest is 6. Node 3's time was set to 4 in step 1 and improved in step 2 — that is relaxation working, and why the same node can sit in the heap twice.

Complexity. Each edge can cause at most one push, so the heap holds at most E entries, and each push or pop costs O(log E) = O(log V). Total O(E log V) time, O(V + E) space. For 10^5 edges that is about 1.7 × 10^6 heap steps, against 10^9 for Bellman-Ford's worst case.

Edge cases

• An unreachable node (Example 2) → its time stays infinite: -1.
• n = 1 → the signal is already everywhere: 0.
• Zero-time edges → allowed; Dijkstra needs non-negative, not positive.
• Two edges between the same pair → both are relaxed; the cheaper wins.
• Nodes numbered from 1 → arrays of size n + 1, and take the maximum over dist[1:] so the unused slot 0 (always infinite) does not turn every answer into -1.

Follow-ups: when Dijkstra is not enough

• "Some times can be negative." Dijkstra's promise that a popped node is final breaks. With A → B = 2, A → C = 5 and C → B = −4, a version that never reopens a finished node reports 2 for B, though A → C → B costs 1. Use Bellman-Ford (Approach 1). One extra pass also detects a negative cycle: if anything still improves after n − 1 passes, times can fall forever and no shortest path exists.
• "Cheapest route using at most K stops." Dijkstra keeps one value per node, but here a pricier route with fewer stops can be the one that finishes cheaper. Run Bellman-Ford for exactly K + 1 passes, each reading only the previous pass's prices:

1def cheapest_within_k_stops(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:2    """Follow-up: at most k stops = at most k+1 flights = k+1 rounds of relaxing."""3    cost = [float("inf")] * n4    cost[src] = 05    for _ in range(k + 1):6        prev = cost[:]                           # read only last round's costs7        for u, v, price in flights:8            if prev[u] + price < cost[v]:9                cost[v] = prev[u] + price10    return -1 if cost[dst] == float("inf") else int(cost[dst])

The copy is the whole trick: relaxing against the live array could chain two flights in one pass and quietly break the stop limit. This costs O(K × E).

• "All weights are equal." Use plain BFS: O(V + E), no heap.