DSA Network Delay Time

The problem

Network Delay Time asks how long a signal takes to reach every node in a network. The network is a set of directed links. A directed link can be crossed in one direction only, and each link carries a travel time.

Every node receives the signal at its shortest travel time from the start node. The answer is the largest of those arrival times, because the signal has arrived everywhere only when the slowest node receives it. A node that can never be reached makes the answer minus one.

cases = [
    ([(2, 1, 1), (2, 3, 1), (3, 4, 1)], 4, 2, 2),
    ([(1, 2, 3), (2, 3, 4)], 4, 1, -1),
    ([(1, 2, 1), (1, 3, 4), (2, 3, 1), (3, 4, 2)], 4, 1, 4),
    ([], 1, 1, 0),
]
for links, n, start, expected in cases:
    print("nodes", n, "start", start, "links", links, "-> delay:", expected)

Read the third row slowly. Node 3 is reached in time 2 through node 2, not in time 4 by the direct link. Node 4 then arrives at time 4, and that slowest arrival is the answer.

Intuition: the route with the fewest links is not the fastest route

The first idea counts links. A route with fewer links feels faster, the way fewer stops feels faster on a trip. Travel times break that feeling, because one slow link can cost more than two fast ones.

The two routes to node 3 below come from the third case. The direct route crosses one link and takes time 4. The route through node 2 crosses two links and takes time 2.

direct = 4
via_two = 1 + 1
print("direct route: 1 link, time", direct)
print("via node 2: 2 links, time", via_two)
print("faster route uses more links:", via_two < direct)

Link count is the wrong measure. The only measure is summed travel time along the route. Every method below therefore works with distances, never with hop counts.

Brute force: relax every link, round after round

Relaxing a link means testing whether travelling that link improves the arrival time of its far node. The brute force relaxes every link in every round. It runs one round per node, which is enough rounds for the longest useful route.

No link is ever relaxed in a clever order. The counter records every relaxation test. The method is slow for the same reason it is trustworthy, since no route can hide from a full set of rounds.

def delay_brute(links, n, start):
    dist = [None] * (n + 1)
    dist[start] = 0
    checks = 0
    for _ in range(n - 1):
        for src, dst, w in links:
            checks += 1
            if dist[src] is not None:
                cand = dist[src] + w
                if dist[dst] is None or cand < dist[dst]:
                    dist[dst] = cand
    arrivals = dist[1:]
    if any(v is None for v in arrivals):
        return -1, arrivals, checks
    return max(arrivals), arrivals, checks

links = [(1, 2, 1), (1, 3, 4), (2, 3, 1), (3, 4, 2)]
answer, arrivals, checks = delay_brute(links, 4, 1)
print("arrivals:", arrivals, " delay:", answer, " relaxation tests:", checks)
answer, arrivals, checks = delay_brute([(2, 1, 1), (2, 3, 1), (3, 4, 1)], 4, 2)
print("arrivals:", arrivals, " delay:", answer, " relaxation tests:", checks)

Four nodes and four links cost twelve tests, which is nodes minus one times links. Most of those tests recheck links whose far node stopped improving rounds earlier. The optimal method exists to skip exactly that rechecking.

The optimal solution: settle nodes in arrival order

The distance table holds the earliest known arrival for each node, and a heap that always settles the unsettled node with the smallest arrival next turns those arrivals final one by one. That one sentence is the whole method.

Settling a node makes its arrival final, because no shorter route to it can appear later. Each link out of a settled node is relaxed once. When the heap empties, any node still holding no arrival is unreachable.

import heapq

def delay_time(links, n, start):
    graph = {node: [] for node in range(1, n + 1)}
    for src, dst, w in links:
        graph[src].append((dst, w))
    dist = {node: None for node in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue
        for nxt, w in graph[node]:
            cand = d + w
            if dist[nxt] is None or cand < dist[nxt]:
                dist[nxt] = cand
                heapq.heappush(heap, (cand, nxt))
    if any(v is None for v in dist.values()):
        return -1, dist
    return max(dist.values()), dist

cases = [
    ([(2, 1, 1), (2, 3, 1), (3, 4, 1)], 4, 2, 2),
    ([(1, 2, 3), (2, 3, 4)], 4, 1, -1),
    ([(1, 2, 1), (1, 3, 4), (2, 3, 1), (3, 4, 2)], 4, 1, 4),
    ([], 1, 1, 0),
]
for links, n, start, expected in cases:
    answer, dist = delay_time(links, n, start)
    print("start", start, "-> delay:", answer, "expected:", expected, "match:", answer == expected)

All four cases pass. The second case returns minus one because node 4 holds no arrival when the heap empties. That single missing value decides the whole answer, exactly as the problem states.

Walkthrough: settling the third network node by node

The walk runs the third case from node 1. The state is the arrival table after each node settles. Arrivals are printed in node order, with None for a node not yet reached.

import heapq

links = [(1, 2, 1), (1, 3, 4), (2, 3, 1), (3, 4, 2)]
graph = {node: [] for node in range(1, 5)}
for src, dst, w in links:
    graph[src].append((dst, w))
dist = {node: None for node in graph}
dist[1] = 0
heap = [(0, 1)]
while heap:
    d, node = heapq.heappop(heap)
    if d > dist[node]:
        continue
    for nxt, w in graph[node]:
        cand = d + w
        if dist[nxt] is None or cand < dist[nxt]:
            dist[nxt] = cand
            heapq.heappush(heap, (cand, nxt))
    print("settled node", node, "at", d, "- arrivals:", [dist[k] for k in sorted(dist)])
print("delay:", max(dist.values()))

Node 3 improves from 4 to 2 when node 2 settles. That improvement is the whole lesson of the intuition section, happening inside the table. Node 4 settles last at time 4, and the answer is read off as the largest arrival.

Complexity

The brute force runs n minus 1 rounds over every link, so its time is O(n times E) for E links. The heap method relaxes each link once and pays a heap cost per relaxation, so its time is O(E log n).

The brute force stores one distance per node, so its space is O(n). The heap method stores one distance per node plus a heap that can hold up to one entry per link relaxation, so its space is O(n + E) in the worst case.

for n in [4, 8, 16]:
    links = n - 1
    print("nodes", n, "- brute relaxation tests:", (n - 1) * links, " heap relaxations:", links)

The counts use a chain network, where each node links only to the next. Even there, 16 nodes cost the brute force 225 tests against 15 relaxations. Denser networks widen the gap, because the brute rounds multiply every added link.

Edge cases and pitfalls

Direction is the first pitfall. A link from node 2 to node 1 carries no signal from node 1 to node 2. Reading a directed link backwards invents routes the network does not have.

The second pitfall is the final step. The answer is the largest arrival, not the sum of arrivals and not the arrival of the highest-numbered node. The rows below pin both facts down.

import heapq

def delay_time(links, n, start):
    graph = {node: [] for node in range(1, n + 1)}
    for src, dst, w in links:
        graph[src].append((dst, w))
    dist = {node: None for node in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue
        for nxt, w in graph[node]:
            cand = d + w
            if dist[nxt] is None or cand < dist[nxt]:
                dist[nxt] = cand
                heapq.heappush(heap, (cand, nxt))
    if any(v is None for v in dist.values()):
        return -1, dist
    return max(dist.values()), dist

answer, dist = delay_time([], 1, 1)
print("single node:", answer)
answer, dist = delay_time([(1, 2, 3), (2, 3, 4)], 4, 1)
print("one node unreached:", answer, " arrivals:", [dist[k] for k in sorted(dist)])
answer, dist = delay_time([(2, 1, 1)], 2, 1)
print("link points the other way:", answer)
answer, dist = delay_time([(1, 2, 5), (1, 3, 2)], 3, 1)
print("arrivals:", [dist[k] for k in sorted(dist)], " delay is the largest:", answer)

The last row sums to 7 and ends at node 3 with arrival 2. Neither number is the answer. The delay is 5, the moment the slower of the two nodes receives the signal.