Practice: Network Delay
Dijkstra in action.
A message starts at one computer in a network. Each link takes some time to travel. How long until every computer has the message? If any computer can't be reached, the answer is minus one.

- A message starts at one node
- Links take time
- When has everyone got it?
Shortest times, then the slowest
The time to reach each computer is its shortest path, so this is Dijkstra's algorithm. The heap always gives us the closest computer we haven't finished. Everyone has the message when the furthest one gets it, so the answer is the largest of the shortest times. Run it.
import heapq
def network_delay(links, n, start):
graph = {i: [] for i in range(1, n + 1)}
for a, b, t in links:
graph[a].append((b, t))
best, heap = {}, [(0, start)]
while heap:
time, node = heapq.heappop(heap)
if node in best:
continue
best[node] = time
for nxt, t in graph[node]:
heapq.heappush(heap, (time + t, nxt))
return max(best.values()) if len(best) == n else -1
links = [(1, 2, 4), (1, 3, 1), (3, 2, 2), (2, 4, 1)]
print(network_delay(links, 4, 1))4
Reading the answer
Computer three is reached in one. Computer two is faster through three, at three, rather than four directly. And computer four is reached through two, at four. The slowest is four, so the whole network has the message after four units of time.
| key | value |
|---|---|
| Node 3 | 1 |
| Node 2 | 3, through node 3 |
| Node 4 | 4, through node 2 |
| Answer | the largest: 4 |
Summary
Network delay is Dijkstra, followed by the largest shortest time. If someone is unreachable, it's minus one. Next, more practice problems, starting with the K th largest number.
Key takeaways- Dijkstra for shortest times
- Answer is the max
- -1 if unreachable