Network Delay Time
Find how long a signal takes to reach every node with Dijkstra's algorithm: a min-heap always settles the closest node next.
Problem Understanding
Network Delay Time: there are n nodes labelled 1 to n and a list times of directed edges [u, v, w], meaning a signal from u reaches v after w. A signal is sent from node k. Return the time it takes for all nodes to receive it, or -1 if some node never does.
Example: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 returns 2.
The Intuition: Settle the Closest Node First
The signal spreads along every edge at once, so each node hears it at its shortest-path time from k, and the answer is the slowest of those. That is single-source shortest paths with non-negative weights: Dijkstra's algorithm.
- Keep
dist, the best time found for each node, and a min-heap of(time, node). - Pop the smallest entry. Every other route to that node would go through something at least as far, so its time is final.
- Relax its edges: if going through it reaches a neighbour sooner, update the neighbour and push the new time.
- A popped entry whose time is worse than
distis stale: a better route was found after it was pushed. Skip it.
The heap is what makes "closest unsettled node" cheap to find. Compare BFS, which settles nodes in order of edge count and is the special case where every edge takes 1. The same heap loop, keyed on edge cost alone, builds a minimum spanning tree in Min Cost to Connect All Points.
Interactive Walkthrough
Each node shows its best time so far above it; the heap is listed beside the graph, smallest first. Try Detour to watch a two-edge path beat a direct edge and leave a stale entry behind, or Example 3 for an unreachable node.
Dry Run Table
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
| Pop | Settled | Relaxed | Heap after |
|---|---|---|---|
| (0, 2) | 2 at 0 | 2 → 1: 1, 2 → 3: 1 | (1, 1), (1, 3) |
| (1, 1) | 1 at 1 | none | (1, 3) |
| (1, 3) | 3 at 1 | 3 → 4: 2 | (2, 4) |
| (2, 4) | 4 at 2 | none | empty |
Answer: every node is reached; the latest is node 4 at 2.
The Solution Template
Lazy Dijkstra: push duplicates and skip stale ones. JavaScript and TypeScript have no built-in heap, so a small binary heap is included. C uses the O(n²) array scan instead of a heap, which is fine for n ≤ 100.
Network Delay Time Code
1var networkDelayTime = function(times, n, k) {2 const graph = Array.from({ length: n + 1 }, () => []);3 for (const [u, v, w] of times) graph[u].push([v, w]);4 const dist = Array(n + 1).fill(Infinity);5 dist[k] = 0;6 const heap = [[0, k]];7 while (heap.length) {8 const [d, u] = pop(heap);9 if (d > dist[u]) continue;10 for (const [v, w] of graph[u]) {11 if (d + w < dist[v]) {12 dist[v] = d + w;13 push(heap, [dist[v], v]);14 }15 }16 }17 const ans = Math.max(...dist.slice(1));18 return ans === Infinity ? -1 : ans;19};2021// Minimal binary min-heap on [time, node] pairs.22function push(heap, item) {23 heap.push(item);24 let i = heap.length - 1;25 while (i > 0) {26 const p = (i - 1) >> 1;27 if (heap[p][0] <= heap[i][0]) break;28 [heap[p], heap[i]] = [heap[i], heap[p]];29 i = p;30 }31}3233function pop(heap) {34 const top = heap[0], last = heap.pop();35 if (heap.length) {36 heap[0] = last;37 let i = 0;38 while (true) {39 let m = i;40 const l = 2 * i + 1, r = l + 1;41 if (l < heap.length && heap[l][0] < heap[m][0]) m = l;42 if (r < heap.length && heap[r][0] < heap[m][0]) m = r;43 if (m === i) break;44 [heap[m], heap[i]] = [heap[i], heap[m]];45 i = m;46 }47 }48 return top;49}
Edge Cases & Common Mistakes
- Unreachable nodes: if any node never gets a time, return
-1, not the largest finite one. - Not skipping stale entries: still correct, but each stale pop re-relaxes edges for nothing; check
d > dist[u]first. - Using BFS: fewest edges is not least time when weights differ.
- 1-indexed nodes: nodes run from 1 to
n; size arraysn + 1and ignore index 0 when taking the maximum. - Negative times: Dijkstra assumes non-negative weights, which LeetCode guarantees (0 to 100). With negative edges use Bellman-Ford, as in Cheapest Flights Within K Stops.
Summary
Run Dijkstra from k with a min-heap: pop the closest node, skip it if stale, relax its edges and push improvements. Return the largest distance, or -1 if a node was never reached. O(E log E) time, O(V + E) space.
More practice: DSA interview questions with answers · patterns cheat sheet