Pattern visualizer
Network Delay Time
Every edge weight is positive, which is what makes a greedy choice safe here: whichever unvisited node currently has the smallest known arrival time can never be beaten by a longer route discovered later, so it can be finalized immediately. Track one number per node — its best time so far — start the source at 0 and everyone else at infinity, then repeatedly settle the closest unvisited node and use its edges to try to lower its neighbors' times. Once every node is settled, the answer is the largest of those times: the network isn't fully covered until its slowest node hears the signal. Animated on: 4 nodes, directed travel times 2->1 (1), 2->3 (1), 3->4 (1), signal starts at node 2 — how long until every node has heard it?.
Dijkstra: always settle the closest unvisited node next
Travel times between nodes
A signal starts at node 2 and every edge carries a positive travel time. The question is how long until the LAST node hears it — the answer is the biggest of the shortest arrival times, so this is single-source shortest paths with one extra MAX at the end.
1FUNCTION networkDelayTime(times, n, k):2 dist[c] <- INFINITY FOR ALL c3 dist[k] <- 04 visited <- EMPTY SET5 WHILE LENGTH(visited) != n6 u <- UNVISITED NODE WITH MIN dist[u]7 IF dist[u] = INFINITY8 RETURN -19 ADD u TO visited10 FOR EACH (u, v, w) IN times WHERE u = u11 dist[v] <- MIN(dist[v], dist[u] + w)12 RETURN MAX(dist)
← / → step · space play · Home restart