How long until a signal reaches every tower? Dijkstra's algorithm settles the earliest arrival first, using a min-heap.
▼The problem
LeetCode 743 (Medium). There are n nodes and a list of directed edges (u, v, w): a signal takes w time to travel from u to v. Send a signal from node k. Return the time it takes for all n nodes to receive it, or -1 if some node never does.
Example (made for the video): n = 5, k = 1, edges (1,2,1) (1,3,4) (2,3,2) (2,4,6) (3,5,3). The direct cable 1→3 takes 4, but 1→2→3 takes 1 + 2 = 3, so tower 3's tentative time improves from 4 to 3.
The solution
def network_delay(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
best = {k: 0} # tentative times
heap, done = [(0, k)], set()
while heap:
t, node = heappop(heap) # earliest
if node in done: continue # stale
done.add(node) # settle
for nxt, w in graph[node]:
if t + w < best.get(nxt, inf):
best[nxt] = t + w
heappush(heap, (t + w, nxt))
return max(best.values()) if len(done) == n else -1Transcript
Network Delay Time. Towers are linked by one-way cables, each with a travel time. A signal starts at one tower. How long until every tower hears it? If one never does, return minus one.
Take five towers, starting at one. The cable from one to three takes four. But one to two takes one, and two to three takes two, so the detour gets there sooner, at three.
You could try every route to every tower and keep the fastest, but routes multiply with every branch.
Dijkstra's algorithm is smarter. Keep a min heap of arrival times, and always settle the earliest tower first. Then update the times along its cables. It's safe: cables never take negative time, so nothing found later can arrive sooner.
In code, pop the earliest time and tower. Skip it if it's already settled. Otherwise settle it, and push each neighbor whose time improves. The answer is the largest settled time, or minus one if a tower was missed.
Let's run it. Tower one settles at zero, giving two a time of one, and three a time of four. Two settles at one. Through two, three improves to three, and four gets seven. Three settles at three, and five gets six. Three's old entry pops out stale: skip it. Five settles at six. Four settles last, at seven: the answer.
Each cable pushes at most once, and each heap step costs log V. That's V plus E, times log V time, and V plus E space.
Earliest first, then spread. That's Network Delay Time.