AI Hints
Home›DSA in Python Tutorial›Windows, Words and Networks
DSA in Python · Lesson 117 of 132

Practice: Network Delay

Dijkstra in action.

⏱ 2 min read▶ Video at 2:19:35🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Practice: Network Delay
From the video: Practice: Network Delay
  • 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.

network_delay.pypython
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))
Output
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.

keyvalue
Node 31
Node 23, through node 3
Node 44, through node 2
Answerthe 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
Next up: Practice: Kth Largest Element — a heap of size k