DSA Tracker

Visualize

Network Delay Time

Dijkstra: always settle the closest unvisited node next

time O(V^2 + E)space O(V + E)

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.

Details

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?

Problem:Network Delay TimeMedium

Pattern:Shortest Path

Dijkstra: always settle the closest unvisited node next

step 1 / 12

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.

Pseudocode
1FUNCTION networkDelayTime(times, n, k):
2  dist[c] <- INFINITY FOR ALL c
3  dist[k] <- 0
4  visited <- EMPTY SET
5  WHILE LENGTH(visited) != n
6    u <- UNVISITED NODE WITH MIN dist[u]
7    IF dist[u] = INFINITY
8      RETURN -1
9    ADD u TO visited
10    FOR EACH (u, v, w) IN times WHERE u = u
11      dist[v] <- MIN(dist[v], dist[u] + w)
12  RETURN MAX(dist)

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. 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.
  2. Every node starts at ∞ except the source: dist[2] = 0. From here, the node with the smallest known time is always safe to finalize next — nothing can reach it faster later, since every edge weight is positive.
  3. Among the unvisited nodes, 2 holds the smallest time (0) — that time is now final, so 2 is settled next.
  4. Arriving at 2 at time 0, each outgoing edge offers a new arrival time at its target: 1 via 1 -> 1, 3 via 1 -> 1. 1 improves to 1 and 3 improves to 1, so those update.
  5. Among the unvisited nodes, 1 holds the smallest time (1) — that time is now final, so 1 is settled next.
  6. 1 has no outgoing edges, so settling it changes nothing else. Move on.
  7. Among the unvisited nodes, 3 holds the smallest time (1) — that time is now final, so 3 is settled next.
  8. Arriving at 3 at time 1, each outgoing edge offers a new arrival time at its target: 4 via 1 -> 2. 4 improves to 2, so that updates.
  9. Among the unvisited nodes, 4 holds the smallest time (2) — that time is now final, so 4 is settled next.
  10. 4 has no outgoing edges, so settling it changes nothing else. Move on.
  11. All 4 nodes are now visited with a final time — the WHILE loop's job is done.
  12. Every node was reached, so the answer is the slowest of the final times: MAX(1, 0, 1, 2) = 2. That is how long the LAST node waits. RETURN 2.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Network Delay Time in the editorAll Graph problemsBack to roadmap