Network Delay Time — The Telegraph Network

Boss 3: The Telegraph Network

This is the boss the whole dungeon was built around. Dungeon 11 gave you BFS, which measures distance by counting hops. Dungeon 10 gave you the heap. Dungeon 14 closed with a promise: "Dijkstra is just greedy with a priority queue." Boss 3 is where that check gets cashed.

And you've already fought half of it. Boss 2's Prim ran a heap-driven settle loop to grow a spanning tree. Dijkstra is the same loop with one line changed. Spot the line and this boss is yours.

The story

It's 1907. You run the head telegraph office in the capital, and a storm warning just landed on your desk. Every station in the region must hear it.

The stations are wired together, but the wires are nothing alike: some are short copper runs, others sag across whole valleys. Each wire has a known relay delay in minutes. Your operators are the best in the country — the instant a message clicks in, they key it onward on every outgoing wire. No coffee breaks. No delay but the wire itself.

The signal fans out from your office along every route at once, and each station learns the news at the earliest moment any route delivers it.

Two questions decide whether the region survives the storm. When does the last station hear the warning? And is there some forgotten outpost the wires never reach at all?

The problem, dressed up properly

You are given a network of n nodes labeled 1 to n, and a list times where times[i] = (u, v, w) means a directed edge from u to v with travel time w. A signal starts at node k. Return the time it takes for all nodes to receive the signal. If that's impossible, return -1.

LeetCode 743, "Network Delay Time". The canonical single-source shortest path problem wearing a telegraph operator's visor.

The naive attempt

BFS conquered Dungeon 11, so reach for it again: spread outward level by level, record the time each station is first reached.

from collections import deque, defaultdict
 
def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
 
    arrival = {k: 0}
    queue = deque([k])
    while queue:
        node = queue.popleft()
        for nxt, w in graph[node]:
            if nxt not in arrival:            # first visit wins
                arrival[nxt] = arrival[node] + w
                queue.append(nxt)
 
    return max(arrival.values()) if len(arrival) == n else -1

Here's the graph that kills it. Office 1, station 2, and a relay hut 3:

• wire 1 → 2, delay 10
• wire 1 → 3, delay 1
• wire 3 → 2, delay 2

BFS pops 1, visits 2 first (one hop, arrival 10), then 3. When the route through the hut shows up offering arrival 3, the "first visit wins" rule slams the door — station 2 is already marked. BFS answers 10. The telegraph answers 3. BFS's whole guarantee was "fewer hops = closer", and weighted wires shred it: one long wire can lose to three short ones.

You could patch it by re-relaxing every edge again and again, n - 1 full sweeps, until nothing improves. That's correct — it's the seed of Bellman-Ford, and it stars in Boss 6 — but it's O(V·E) of brute patience. The telegraph office can do better than patience.

The weapon: Dijkstra, greedy with a priority queue

Recover the one thing that made BFS work: it settled nodes in increasing order of distance. The queue handed them over nearest-first for free, because every edge cost 1. Weighted edges broke the free part, not the idea.

So buy the ordering back. Replace the FIFO queue with the min-heap from Dungeon 10, keyed by total delay from the source. Then run Dungeon 14's greedy argument:

Pop the unsettled node with the smallest tentative delay d. That delay is final. Any other route to this node would have to leave through some node still in the heap — and everything in the heap already sits at delay d or worse, with non-negative wire delays only adding more.

That's an exchange-free greedy proof, the kind Dungeon 14 drilled: the smallest popped value can never be beaten later, so commit to it and never look back. Each settled node then offers its neighbors new candidate routes, pushed into the heap.

One practical wrinkle: a node can get pushed several times as better routes appear, and Python's heapq can't cheaply delete the outdated copies. Don't bother. Let them sit, and when a popped node is already settled, skip it. Lazy deletion — stale entries die of embarrassment on arrival.

import heapq
from collections import defaultdict
 
def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
 
    dist = {}                          # node -> settled shortest delay
    heap = [(0, k)]
    while heap:
        d, node = heapq.heappop(heap)
        if node in dist:
            continue                   # lazy deletion: stale entry
        dist[node] = d                 # settled, final, forever
        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

Now put it next to Boss 2. Prim's loop popped (edge_weight, node) and grew a tree by cheapest single edge. Dijkstra pops (total_delay, node) and grows a shortest-path frontier by cheapest whole route. Same heap, same settle-and-skip, same neighbor push. The entire difference is one expression: push w versus push d + w. That's the promise from Dungeon 14's finale, kept literally.

Watching it work

Five stations, office is k = 1. Wires: 1→2 (2), 1→3 (5), 2→3 (1), 2→4 (7), 3→4 (2), 4→5 (1).

All five stations settled: delays 0, 2, 3, 5, 6. The last station to hear the warning is 5, at minute 6. That max is the answer. Notice the two stale pops doing exactly nothing — lazy deletion in action, the outdated (5, 3) and (9, 4) entries surfacing after better routes already won.

Gotchas

1. Marking visited on push instead of on pop. The BFS habit. In BFS the first push is the best route, so marking early is safe. With weights, the first push to a node may be a lousy route — station 3 above was pushed at 5 before the true 3 arrived. Mark on push and you freeze the bad number in. Settlement happens at pop time, when the heap has proven minimality.

2. Forgetting the stale-entry skip. Without if node in dist: continue, every stale copy gets fully re-expanded: neighbors re-pushed, work multiplied, and on dense graphs the heap snowballs. The answer may even survive, which is worse — it hides the bug until a timeout. The skip line is two tokens of insurance; never ship Dijkstra without it.

3. Returning the wrong number at the end. The question is when the last station hears the message: the max over all settled delays, not the delay to any single target and certainly not their sum. And if fewer than n stations ever settled, some outpost is unreachable — that's the -1, and it's checked with len(dist) == n, not by hoping the heap complains.

4. Trusting it with negative weights. Everything above rests on "more wire never means less delay". Feed in a negative edge and settled nodes are no longer final, silently. Dijkstra won't crash. It will just be wrong, which is the most dangerous way an algorithm can fail. Negative edges need Bellman-Ford, three bosses from now.

Complexity

Every edge pushes at most one heap entry, so the heap holds O(E) items, and each push or pop costs O(log E) = O(log V²) = O(log V).

Time: O(E log V). Space: O(V + E) for the graph, distances, and heap.

Boss down

The last station keys back its acknowledgment at minute six, and the storm warning beats the storm. The centerpiece weapon of Dungeon 15 is now on your belt: Dijkstra, which is nothing but Dungeon 14's greedy commitment served on Dungeon 10's heap, replacing BFS's hop-counting with true weighted distance. One loop, three dungeons deep.

Next up, Boss 4: Swim in Rising Water — The Flooded Quarry. The quarry is filling, and you must cross as the water climbs. Dijkstra warps: the cost of a path is no longer the sum of its edges but the maximum single edge along it — and the settle loop barely notices the difference. See you at the waterline.