Network Delay Time: Dijkstra on a Weighted Directed Graph
Solve Network Delay Time with Dijkstra's algorithm — intuition, a worked priority-queue walkthrough, JavaScript code, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Picture a signal fired from one server that has to ripple across an entire network. Each cable has a fixed travel time. The question sounds like a puzzle but it's the single most reused graph problem in interviews: how long until every node has heard the signal?
That "how long until all of them" phrasing is the whole trick. The answer is the time it takes the slowest node to receive the signal — which is the longest of all the shortest paths from the source. To get every shortest path from one starting node, you reach for Dijkstra's algorithm.
Master the reasoning here and you've unlocked the template behind weighted-shortest-path problems, flight routing, and half the graph questions on any interview list.
The problem
You're given n nodes labeled 1 to n, and a list times where each entry [u, v, w] is a directed edge: a signal from node u reaches node v after w units of time. Starting from a source node k, return the minimum time for all n nodes to receive the signal. If some node can never be reached, return -1.
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
// From node 2: node 1 arrives at t=1, node 3 at t=1,
// node 4 (via 2→3→4) at t=2. The last arrival is t=2.Two details drive the whole solution:
- Edges are directed and weighted — the cost from
utovis not symmetric, and you're summing weights, not counting hops. - The answer is a maximum over minimums: for each node compute its shortest arrival time, then take the largest. If any node stays unreachable (
Infinity), the answer is-1.
The brute force baseline
You could run Bellman-Ford: relax every edge n-1 times so distances settle.
function networkDelayTime(times, n, k) {
const dist = new Array(n + 1).fill(Infinity);
dist[k] = 0;
// Relax all edges n-1 times
for (let i = 0; i < n - 1; i++) {
for (const [u, v, w] of times) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
let res = 0;
for (let i = 1; i <= n; i++) res = Math.max(res, dist[i]);
return res === Infinity ? -1 : res;
}This is correct and refreshingly simple, but it's O(n · E): for every one of n-1 passes it scans all edges, even edges whose endpoints already have their final distance. Bellman-Ford earns its keep only when edges can have negative weights. Here every weight is positive, so we can do much better by being greedy.
The key insight: settle the closest node first
Dijkstra's algorithm rests on one invariant. If all edge weights are non-negative, then the unvisited node with the smallest known distance already has its final answer. Nothing you discover later can offer a shorter route to it — any other path would have to pass through a node that is already farther away, and adding a positive weight only makes things longer.
So instead of blindly re-scanning every edge, always process the cheapest-to-reach node next. A min-priority-queue hands you that node in one step. When you pop it, its distance is locked in, and you "relax" its outgoing edges — checking whether going through it gives any neighbor a shorter arrival time.
This is the greedy, expand-the-frontier pattern. The queue is ordered by cumulative time, not insertion order, and that ordering is what makes each popped distance provably final.
The optimal solution
Here's the exact algorithm the visualizer traces — a distance array plus a priority queue kept sorted by time:
function networkDelayTime(times, n, k) {
const adj = Array.from({ length: n + 1 }, () => []);
for (const [u, v, w] of times) {
adj[u].push([v, w]);
}
// Arrays for tracking min distance to each node
const dist = new Array(n + 1).fill(Infinity);
dist[k] = 0;
// Min-Queue of [distance, node], seeded with start node
const pq = [[0, k]];
// Dijkstra's Algorithm
while (pq.length > 0) {
// Extract node with minimum distance
pq.sort((a, b) => a[0] - b[0]);
const [currDist, u] = pq.shift();
// This is not the shortest path we know anymore
if (currDist > dist[u]) continue;
// Relax all outgoing edges
for (const [v, weight] of adj[u]) {
const nextDist = currDist + weight;
if (nextDist < dist[v]) {
dist[v] = nextDist;
pq.push([nextDist, v]);
}
}
}
// Find the max time it took to reach a node
let res = 0;
for (let i = 1; i <= n; i++) {
res = Math.max(res, dist[i]);
}
return res === Infinity ? -1 : res;
}Three lines carry the design:
- The adjacency list groups each node's outgoing edges so relaxation is a quick local scan, not a filter over the whole
timesarray. if (currDist > dist[u]) continue;is the stale-entry guard. Dijkstra pushes a new[distance, node]pair every time a node's distance improves, so the queue can hold several entries for the same node. When you pop one whosecurrDistis worse than the best distance you've already recorded, it's outdated — skip it.- The final loop turns per-node shortest times into the single answer: the maximum, or
-1if any node is stillInfinity.
Sorting the array on every iteration is O(pq log pq) and stands in for a real binary heap; the logic is identical and the trace is easier to read.
Walkthrough
Trace times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2. The adjacency list is 2 → [(1,1), (3,1)], 3 → [(4,1)]. Start with dist[2] = 0 and pq = [[0,2]].
| Pop | currDist, u | Guard skip? | Edges relaxed | dist after (nodes 1–4) | pq after |
|---|---|---|---|---|---|
| 1 | 0, node 2 | no | 2→1 sets dist[1]=1; 2→3 sets dist[3]=1 | [1, 0, 1, ∞] | [[1,1],[1,3]] |
| 2 | 1, node 1 | no | none (no outgoing edges) | [1, 0, 1, ∞] | [[1,3]] |
| 3 | 1, node 3 | no | 3→4 sets dist[4]=2 | [1, 0, 1, 2] | [[2,4]] |
| 4 | 2, node 4 | no | none | [1, 0, 1, 2] | [] |
The queue is empty, so the loop ends. Final distances are dist[1]=1, dist[2]=0, dist[3]=1, dist[4]=2. The maximum is 2 — node 4 is the last to hear the signal, and none stayed at Infinity, so the answer is 2.
Notice pop 1 pushed two entries with equal cost. Because the queue is sorted by time, node 4 (cost 2) is never touched until nodes 1 and 3 (cost 1) are fully settled — the greedy ordering enforces itself.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Bellman-Ford | O(n · E) | O(n) | relax all E edges across n-1 passes |
| Dijkstra (this code) | O(E · V) | O(V + E) | sort() on each pop makes the queue step linear-ish; a real heap gives O((V+E) log V) |
| Dijkstra with a binary heap | O((V + E) log V) | O(V + E) | log-time push/pop over up to E queue entries |
Here V = n nodes and E = times.length edges. Space is the adjacency list (O(V + E)), the distance array (O(V)), and the queue (up to O(E) entries). Swapping the sorted array for a proper min-heap is the only change needed to hit the textbook O((V+E) log V) bound.
Common mistakes
- Dropping the stale-entry guard. Without
if (currDist > dist[u]) continue;, you re-relax edges from an outdated distance, wasting work and risking wrong intermediate state. It's cheap insurance — keep it. - Sizing arrays to
ninstead ofn + 1. Nodes are labeled1…n, sodistandadjneed indexnto exist. Index0is just an unused slot. - Reaching for Dijkstra with negative weights. The greedy invariant only holds when every weight is non-negative. If an edge could be negative, the "closest node is final" claim breaks and you must fall back to Bellman-Ford.
- Forgetting the unreachable check. If a node never gets relaxed its distance stays
Infinity. ReturningMath.max(...)without testing forInfinityyields a garbage number instead of the required-1. - Confusing hops with time. A path with more edges can still be faster. You compare summed weights, never edge counts.
Where this pattern shows up next
Weighted-graph traversal branches in a few directions from here:
- Cheapest Flights Within K Stops — shortest path with an extra constraint on the number of edges, where plain Dijkstra needs a twist.
- Shortest Path in Binary Matrix — the unweighted cousin, where BFS replaces the priority queue because every step costs the same.
- Course Schedule II — a directed graph again, but the goal is a valid ordering via topological sort rather than distances.
- Redundant Connection — undirected graphs and cycle detection through union-find.
You can also step through Network Delay Time interactively to watch the priority queue reorder and each node's distance settle, one relaxation at a time.
FAQ
Why use Dijkstra instead of BFS for Network Delay Time?
BFS finds the fewest edges to each node, which only equals the shortest path when every edge has the same weight. Here edges carry different travel times, so a two-hop route can beat a one-hop route. Dijkstra orders exploration by cumulative time using a priority queue, guaranteeing that the first time you finalize a node you've found its true minimum arrival time.
What is the time complexity of the Dijkstra solution?
With a real binary min-heap it's O((V + E) log V), where V = n is the node count and E is the number of edges. The version shown sorts the queue array on each pop, which is simpler to read but slightly slower. Space is O(V + E) for the adjacency list, distance array, and queue.
When does Network Delay Time return -1?
When at least one node can never receive the signal. After Dijkstra finishes, any node still holding Infinity in the distance array was unreachable from the source k — no directed path leads to it. Since the problem asks for the time until all nodes are covered, an unreachable node makes that impossible, so the answer is -1.
Why does the code push multiple entries for the same node?
Dijkstra improves a node's distance whenever it finds a shorter route, and each improvement pushes a fresh [distance, node] pair rather than updating an existing one — a lazy-deletion trick that avoids costly decrease-key operations. Old, larger-distance entries linger in the queue. The if (currDist > dist[u]) continue; guard discards those stale pops so each node's edges are relaxed only from its final, smallest distance.
Can Dijkstra handle negative edge weights here?
No. Dijkstra's correctness depends on the assumption that extending any path only adds cost, so the closest unsettled node is always final. A negative weight breaks that — a later, longer-looking path could actually be cheaper. Network Delay Time uses positive travel times, so Dijkstra is safe; for graphs that allow negative edges you'd switch to Bellman-Ford.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.