Network Delay Time
Network Delay Time: compute when all nodes receive a signal sent from one node through weighted directed edges.
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- times[i].length == 3
- 1 <= ui, vi <= n
- ui != vi
- 0 <= wi <= 100
- All the pairs (ui, vi) are unique. (i.e., no multiple edges.)
Intuition
Network delay time sends a signal from one node through a weighted directed graph and asks when the last node receives it. Each node hears the signal at its shortest-path distance from the source, so the answer is the maximum of those distances — and −1 if any node is unreachable.
The first thing to rule out is BFS. Breadth-first search finds the path with the fewest edges, which is not the fastest path when edges have different weights. A two-hop route of weight 1 each beats a single hop of weight 10, and BFS would wrongly prefer the single hop.
Since the weights are non-negative, Dijkstra's algorithm is the right tool. It repeatedly settles the closest unfinalised node, and the guarantee that makes it work is:
- When a node is popped with the smallest known distance, that distance is final — no later path can improve it, because every remaining route starts by leaving an already-more-distant node and weights never subtract.
A min-heap keyed by distance provides that node in O(log n).
Two implementation points matter. Edges are directed, so a triple (u, v, w) creates one adjacency entry, not two — adding both is a quiet bug that produces shorter answers than the truth. And a node can enter the heap several times through different paths, so skip a popped node that is already finalised rather than reprocessing it.
At the end, if fewer than n nodes were finalised, some node never heard the signal and the answer is −1.
Single-source minimum arrival times with nonnegative weighted edges point directly to Dijkstra's algorithm. A request for the time until everyone is reached asks for the maximum finite shortest-path distance.
Approach
Before reading on: price up what the brute force costs here, then ask whether the weights force you past a plain breadth-first sweep. Aim for O((V + E) log V) time and O(V + E) space.
Rule out plain BFS
BFS minimises the number of edges, not the total weight. With varied weights the fewest-hops path is often slower, so BFS gives a wrong answer here even though it looks like a graph traversal problem.
Build a directed adjacency list
For each (u, v, w), store (v, w) under u only. Adding the reverse edge as well is a common slip that invents routes the network does not have, producing an answer that is too small.
Run Dijkstra from the source
Seed a min-heap with (0, source). Repeatedly pop the smallest tentative distance and relax that node's outgoing edges, pushing (distance + weight, neighbour) for each.
Skip already-finalised nodes
A node can be pushed several times via different paths. When popped, if it already has a final distance, discard the entry — this lazy-deletion approach is simpler and faster than trying to decrease keys inside the heap.
Understand why popping settles a node
With non-negative weights, any alternative route to a popped node would have to pass through a node still in the heap, which is already at least as far away. So the popped distance cannot be improved — this is the property Dijkstra rests on, and it fails if any weight is negative.
Take the maximum, or report −1
If exactly n nodes were finalised, the largest distance is when the last node receives the signal. If fewer, some node is unreachable and the answer is −1 — check the count, not whether any distance is infinite.
Cost of the search
Each edge can push one heap entry, giving O(E log V) time and O(V + E) space. Bellman-Ford would also work here at O(V·E), and is the choice if the problem ever allows negative weights.
Solution & live demo
Common pitfalls
Treating edges as undirected
graph[v].append((u, w))
graph[u].append((v, w))
The listed travel time applies only in the given direction.
Using edge count instead of weight
heappush(heap, (cost + 1, neighbor))
heappush(heap, (cost + weight, neighbor))
Arrival time accumulates the provided edge weights.
Returning a maximum for a disconnected graph
return max(distance.values())
return max(distance.values()) if len(distance) == n else -1
Missing nodes mean the signal never reaches the entire network.
Edge cases
Its distance is zero, so the delay is zero.
Both candidates may enter the heap, and the lower arrival is finalized first.
It never becomes finalized, so return -1.