DevOps NetworkDevOpsNetwork
Join Free
Advanced

Network Delay Time

mediumAdvanced graphs Must-do

Problem statement

A cluster has n servers numbered 1 to n. The list times describes one-way links: each entry [u, v, w] means a message sent from server u reaches server v after w milliseconds. Links are directed, so [u, v, w] says nothing about going from v back to u.

Server k broadcasts a message at time 0, and every server forwards it along all its outgoing links the moment it arrives. Return how many milliseconds it takes until every server has received the message. If some server can never receive it, return -1.

Each server receives the message at the earliest time any path can deliver it, so the answer is the largest of the shortest-path distances from k.

Examples

Example 1

Input: times = [[1,2,3],[1,3,9],[2,3,4],[3,4,2]], n = 4, k = 1

Output: 9

Explanation: Server 2 gets it at 3. Server 3 gets it at 7 through server 2, which beats the direct 9 ms link. Server 4 gets it at 7 + 2 = 9, the last arrival.

Example 2

Input: times = [[1,2,5],[3,2,1]], n = 3, k = 1

Output: -1

Explanation: No link leads into server 3, so it never hears the broadcast.

Hints

Approach

Dijkstra with a min-heap. Build an adjacency list, then push (0, k) onto a heap of (time, server) pairs.

  1. Pop the pair with the smallest time.
  2. If that server is already finalised, skip it (a stale, slower entry).
  3. Otherwise record its time as final and push (time + w, neighbour) for each outgoing link to an unfinalised neighbour.

Because weights are non-negative, nothing popped later can be earlier, so the first pop of each server is its true arrival time. When the heap empties, if all n servers were finalised, the answer is the largest recorded time; otherwise return -1.

ComplexityTime O(E log E)Space O(n + E)
Python
import heapq
from collections import defaultdict
def network_delay_time(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
arrival = {}
heap = [(0, k)]
while heap:
t, node = heapq.heappop(heap)
if node in arrival:
continue
arrival[node] = t
for nxt, w in graph[node]:
if nxt not in arrival:
heapq.heappush(heap, (t + w, nxt))
return max(arrival.values()) if len(arrival) == n else -1
print(network_delay_time([[1, 2, 3], [1, 3, 9], [2, 3, 4], [3, 4, 2]], 4, 1))
print(network_delay_time([[1, 2, 5], [3, 2, 1]], 3, 1))

Follow-up questions

  • Return the actual path the message took to the slowest server (keep a parent map when you finalise a node).
  • What changes if some links can have negative weight? (Dijkstra breaks; use Bellman-Ford, which can also detect negative cycles.)

Frequently asked questions

It is shortest-path routing with a thin disguise: latency between hosts, propagation of a config push through a gossip network, or how long a failover signal takes to reach every node. Link-state routing protocols such as OSPF run Dijkstra for the same reason. It is also the standard way to check that you know Dijkstra's algorithm, and not only BFS.

BFS finds the path with the fewest links, not the lowest total weight. In the first example BFS reaches server 3 over the direct 9 ms link, but the two-hop route through server 2 takes only 7 ms. BFS is only correct when every weight is equal.

Python's heapq has no decrease-key, so the same server can be pushed several times with different times. The first pop carries the smallest time; later pops are stale entries and must be ignored, or you would overwrite a correct answer with a worse one.