The problem. A network has n nodes, labelled 1 to n. Each entry [u, v, w] in times means a signal sent from u reaches v after w units of time (one way only). A signal starts at node k. Return how long it takes until every node has received it, or -1 if some node never does.
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 -> 2
times = [[1,2,1]], n = 2, k = 1 -> 1
times = [[1,2,1]], n = 2, k = 2 -> -1 (nothing leaves node 2)Each node hears the signal at its shortest-path time from k, so the answer is the largest of those times. The edges have different weights, and that breaks plain BFS: BFS assumes fewer edges means shorter, but in the picture the route with more edges (1 → 3 → 2) beats the direct one.
Dijkstra's algorithm keeps BFS's spirit — settle the nearest things first — using distance instead of edge count. Keep a best-known distance for every node, and a min-heap of nodes ordered by that distance. Repeatedly pop the closest node: its distance is now final, because any other route to it would have to continue from a node that is already at least as far away, and weights are never negative. Then relax its edges: if going through it gives a neighbour a shorter distance, record that and push the neighbour.
Two practical details. A node can be pushed more than once as its distance improves; when an out-of-date entry is popped later, just skip it. And Dijkstra needs weights that are zero or more — one negative edge can make a settled node's distance wrong. JavaScript has no built-in heap, so the code uses the small Heap class from the Heap course.
A simpler idea that needs no heap. Go through every edge and relax it: if dist[u] + w beats dist[v], lower dist[v]. One pass fixes every shortest path that uses one edge; the next pass, two edges; and so on. A shortest path never needs more than n - 1 edges, so n - 1 passes are enough — stop early if a pass changes nothing.
function networkDelayTime(times, n, k) { const dist = new Array(n + 1).fill(Infinity); dist[k] = 0; for (let round = 1; round < n; round++) { // a shortest path uses at most n - 1 edges let changed = false; for (const [u, v, w] of times) { if (dist[u] + w < dist[v]) { // relax: a cheaper way to reach v through u dist[v] = dist[u] + w; changed = true; } } if (!changed) break; // nothing improved: every distance is final } const slowest = Math.max(...dist.slice(1)); return slowest === Infinity ? -1 : slowest;}Time O(V · E), space O(V). Up to V - 1 passes over all E edges. Slower than Dijkstra, but it copes with negative weights — and the idea of counting passes returns in Pattern 9.
Push [0, k]. Pop the closest entry; skip it if it's out of date; otherwise relax each edge leaving it. When the heap is empty, every reachable node has its final time.
The heap always hands back the closest unsettled node. Try the example where the longer route is faster.
function networkDelayTime(times, n, k) { const adj = Array.from({ length: n + 1 }, () => []); for (const [u, v, w] of times) adj[u].push([v, w]); const dist = new Array(n + 1).fill(Infinity); dist[k] = 0; const heap = new Heap((a, b) => a[0] - b[0]); // [distance, node], closest first heap.push([0, k]); while (heap.size() > 0) { const [d, u] = heap.pop(); if (d > dist[u]) continue; // a stale entry: u was already reached cheaper for (const [v, w] of adj[u]) { if (d + w < dist[v]) { // a cheaper way to reach v, through u dist[v] = d + w; heap.push([dist[v], v]); } } } const slowest = Math.max(...dist.slice(1)); return slowest === Infinity ? -1 : slowest;}Time O(E log V), space O(V + E). Each edge can push one heap entry, and each push or pop costs O(log E) = O(log V). The adjacency list and the heap take O(V + E).
Use Dijkstra whenever all weights are non-negative — that's most interview questions. Reach for Bellman-Ford when weights can be negative, or when the path may use only a limited number of edges (next pattern).
n = 1: the signal is already everywhere, so the answer is 0.[2,1,1] lets 2 reach 1, not 1 reach 2.