208. Network Delay Time

Why this mechanism works

Each node receives the signal at its shortest travel time from the source. Parallel propagation means total completion time is the maximum of those shortest distances, not their sum. Translate one-based labels at the boundary and reuse Dijkstra's nonnegative-weight protocol.

State and boundaries

The zero-based adjacency models the same directed network. distances[v] is the earliest arrival time at node v+1.

Protocol

1. Convert each label to zero-based adjacency.
2. Run Dijkstra from start-1.
3. Return -1 if any distance is None.
4. Otherwise return the maximum distance.

Visualization

source 2 -> 1 in 1; source 2 -> 3 in 1; 3 -> 4 in 1
arrival times [1,0,1,2]
all reached at time max=2

Python implementation

from kata_207 import dijkstra

def network_delay(n, edges, start):
    adj = [[] for _ in range(n)]
    for u, v, delay in edges:
        adj[u - 1].append((v - 1, delay))
    distances = dijkstra(adj, start - 1)
    return -1 if any(value is None for value in distances) else max(distances)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 network_delay: adj = [[] for _ in range(n)]
n=4; edges=[(2, 1, 1), (2, 3, 1), (3, 4, 1)]; start=2; _=0

L4 network_delay: adj = [[] for _ in range(n)]
n=4; edges=[(2, 1, 1), (2, 3, 1), (3, 4, 1)]; start=2; _=1

L4 network_delay: adj = [[] for _ in range(n)]
n=4; edges=[(2, 1, 1), (2, 3, 1), (3, 4, 1)]; start=2; _=2

L4 network_delay: adj = [[] for _ in range(n)]
n=4; edges=[(2, 1, 1), (2, 3, 1), (3, 4, 1)]; start=2; _=3

L4 network_delay: adj = [[] for _ in range(n)]
n=4; edges=[(2, 1, 1), (2, 3, 1), (3, 4, 1)]; start=2; adj=[[], [], [], []]

L5 network_delay: for u, v, delay in edges:
n=4; edges=[(2, 1, 1), (2, 3, 1), (3, 4, 1)]; start=2; adj=[[], [], [], []]; u=2; v=1; delay=1

L6 network_delay: adj[u - 1].append((v - 1, delay))
n=4; edges=[(2, 1, 1), (2, 3, 1), (3, 4, 1)]; start=2; adj=[[], [(..., ...)], [], []]; u=2; v=1; delay=1

L5 network_delay: for u, v, delay in edges:
n=4; edges=[(2, 1, 1), (2, 3, 1), (3, 4, 1)]; start=2; adj=[[], [(..., ...)], [], []]; u=2; v=3; delay=1

... 5 intermediate state changes omitted ...

L8 <genexpr>: return -1 if any(value is None for value in distances) else max(distances)
.0=list_iterator; value=0

L8 <genexpr>: return -1 if any(value is None for value in distances) else max(distances)
.0=list_iterator; value=1

L8 <genexpr>: return -1 if any(value is None for value in distances) else max(distances)
.0=list_iterator; value=2

L8 <genexpr>: return -1 if any(value is None for value in distances) else max(distances)
.0=list_iterator; value=2

L4 network_delay: adj = [[] for _ in range(n)]
n=2; edges=[(1, 2, 1)]; start=2; _=0

L4 network_delay: adj = [[] for _ in range(n)]
n=2; edges=[(1, 2, 1)]; start=2; _=1

L4 network_delay: adj = [[] for _ in range(n)]
n=2; edges=[(1, 2, 1)]; start=2; adj=[[], []]

L5 network_delay: for u, v, delay in edges:
n=2; edges=[(1, 2, 1)]; start=2; adj=[[], []]; u=1; v=2; delay=1

L6 network_delay: adj[u - 1].append((v - 1, delay))
n=2; edges=[(1, 2, 1)]; start=2; adj=[[(..., ...)], []]; u=1; v=2; delay=1

L7 network_delay: distances = dijkstra(adj, start - 1)
n=2; edges=[(1, 2, 1)]; start=2; adj=[[(..., ...)], []]; u=1; v=2; delay=1; distances=[None, 0]

L8 <genexpr>: return -1 if any(value is None for value in distances) else max(distances)
.0=list_iterator; value=None

Why the solution is correct

Dijkstra gives the earliest achievable arrival at every reachable node. All nodes have received the signal exactly when the last of these arrivals occurs, so their maximum is necessary and sufficient. An unreachable node can never receive the signal.

Time and space

O(n+E log(E+2)) time and O(n+E) space, inherited from adjacency construction and lazy-heap Dijkstra.

Common mistakes

Summing arrival times incorrectly serializes concurrent propagation. Forgetting to convert both endpoints and the start mixes label conventions.

Reasoning card

Transfer exercise

Allow several initial sources by initializing each at distance zero in the same heap.