Dijkstra's Algorithm: Shortest Paths with a Min-Heap
Dijkstra's algorithm for shortest paths on a weighted graph, explained with a min-heap — intuition, JavaScript code, a full walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
BFS finds the shortest path when every edge costs the same. The moment edges carry different weights — road distances, network latency, ticket prices — BFS breaks, because the path with the fewest hops is no longer the cheapest.
Dijkstra's algorithm fixes exactly that. It computes the minimum-cost path from one source node to every other node in a graph with non-negative edge weights, and it does so greedily: always expand outward from the closest unfinished node next. That single ordering rule is what makes it correct, and a min-heap is what makes it fast.
The problem
You're given a weighted directed graph as an adjacency list. graph[u] is a list of [neighbor, weight] pairs meaning there's an edge from u to neighbor costing weight. Starting from source node 0, return an array dist where dist[i] is the length of the shortest path from 0 to i (or Infinity if i is unreachable).
Input: graph = [
[[1, 4], [2, 1]], // node 0 -> node 1 (w=4), node 0 -> node 2 (w=1)
[[3, 1]], // node 1 -> node 3 (w=1)
[[1, 2], [3, 5]], // node 2 -> node 1 (w=2), node 2 -> node 3 (w=5)
[] // node 3 has no outgoing edges
]
Output: [0, 3, 1, 4]The interesting answer is dist[1] = 3. The direct edge 0 → 1 costs 4, but routing 0 → 2 → 1 costs 1 + 2 = 3. The cheapest route is not the most direct one — that gap is the whole reason a greedy scan needs to be careful about order.
The brute force baseline
The core loop is fixed: repeatedly pick the closest unvisited node, then relax its edges. The naive way to "pick the closest" is to scan the entire distance array every time.
function dijkstraSlow(graph, src) {
const n = graph.length;
const dist = new Array(n).fill(Infinity);
const visited = new Array(n).fill(false);
dist[src] = 0;
for (let iter = 0; iter < n; iter++) {
// Linear scan for the nearest unvisited node
let node = -1;
for (let i = 0; i < n; i++) {
if (!visited[i] && (node === -1 || dist[i] < dist[node])) node = i;
}
if (node === -1 || dist[node] === Infinity) break;
visited[node] = true;
for (const [neighbor, weight] of graph[node]) {
if (dist[node] + weight < dist[neighbor]) {
dist[neighbor] = dist[node] + weight;
}
}
}
return dist;
}This is correct, but that inner "find the minimum" scan walks all V nodes on every one of the V iterations — O(V²) total, regardless of how few edges the graph actually has. On a sparse graph with 100,000 nodes and only 200,000 edges, you still pay ten billion comparisons finding minimums. The relaxation work is cheap; the selection is the bottleneck.
The key insight: let a heap pick the minimum
We don't need to re-scan the whole array to find the closest node. We need a data structure that hands us the smallest tentative distance in O(log V) and lets us insert new candidates just as cheaply. That's a min-heap (priority queue) keyed on distance.
The heap stores [distance, node] pairs. Pop the smallest, finalize that node, and push its improved neighbors back on. Because every edge weight is non-negative, the first time a node comes off the heap its distance is already optimal — no shorter path can arrive later, since every remaining route is at least as long as what we just popped. That guarantee is why Dijkstra locks a node the moment it's extracted.
One wrinkle: this heap never deletes or updates old entries. When we find a better distance to a node, we push a new pair and leave the old, larger one behind. So a node can appear in the heap more than once. We handle those stale entries with a one-line guard — if a popped distance is worse than the best we've already recorded, we skip it.
The optimal solution
This mirrors the code in the visualizer exactly: a MinHeap, a dist array seeded to Infinity, and the pop-check-relax loop.
function dijkstras(graph, src) {
const n = graph.length;
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
const pq = new MinHeap(); // stores [distance, node], ordered by distance
pq.push([0, src]);
while (pq.size()) {
const [nodeDist, node] = pq.pop();
// Stale entry: we already locked a shorter path to `node`
if (nodeDist > dist[node]) continue;
for (const [neighbor, weight] of graph[node]) {
const newDist = dist[node] + weight;
if (newDist < dist[neighbor]) {
dist[neighbor] = newDist; // relax
pq.push([newDist, neighbor]);
}
}
}
return dist;
}Three lines carry the whole algorithm. pq.pop() gives the globally closest unfinished node. nodeDist > dist[node] throws away the duplicate, out-of-date pairs the lazy heap accumulated. And newDist < dist[neighbor] is the relaxation check — the only time we ever improve a distance and enqueue more work. A node is considered finalized the first time it survives the stale check.
Walkthrough
Tracing graph = [[[1,4],[2,1]], [[3,1]], [[1,2],[3,5]], []] from source 0. The heap column shows [dist, node] pairs, smallest first.
| Pop | node, nodeDist | Stale? | Relaxations | dist after | Heap after |
|---|---|---|---|---|---|
| — | (seed) | — | dist[0]=0 | [0, ∞, ∞, ∞] | [0,0] |
| 1 | node 0, d=0 | no | 0→1: 4<∞ · 0→2: 1<∞ | [0, 4, 1, ∞] | [1,2] [4,1] |
| 2 | node 2, d=1 | no | 2→1: 3<4 ✓ · 2→3: 6<∞ | [0, 3, 1, 6] | [3,1] [4,1] [6,3] |
| 3 | node 1, d=3 | no | 1→3: 4<6 ✓ | [0, 3, 1, 4] | [4,1] [4,3] [6,3] |
| 4 | node 1, d=4 | yes (4 > dist[1]=3) | skip | [0, 3, 1, 4] | [4,3] [6,3] |
| 5 | node 3, d=4 | no | (no outgoing edges) | [0, 3, 1, 4] | [6,3] |
| 6 | node 3, d=6 | yes (6 > dist[3]=4) | skip | [0, 3, 1, 4] | (empty) |
Two moments matter. On Pop 2, relaxing 2 → 1 improves dist[1] from 4 down to 3 and pushes a fresh [3,1] — the older [4,1] is now obsolete but still sitting in the heap. That obsolete pair resurfaces on Pop 4, where the stale guard (4 > 3) discards it instead of re-processing node 1. Pop 6 does the same for the abandoned [6,3]. The heap empties, and dist = [0, 3, 1, 4] is final.
Complexity
With a binary min-heap on a graph of V nodes and E edges:
| Measure | Big-O | Why |
|---|---|---|
| Time | O((V + E) log V) | each edge can push once → up to E pops/pushes, each O(log V) |
| Space | O(V + E) | adjacency list is O(V + E); heap and dist array add O(V) |
The heap version beats the O(V²) linear scan whenever the graph is sparse (E ≪ V²), which is almost every real graph — road networks, dependency graphs, and routing tables all have far fewer edges than the V² worst case. On dense graphs the two converge, and the plain array scan can even edge ahead by avoiding heap overhead.
Common mistakes
- Using it with negative edges. Dijkstra's correctness depends on never revisiting a locked node. A negative edge could offer a cheaper route to an already-finalized node, and Dijkstra will never look. Use Bellman-Ford for graphs with negative weights.
- Dropping the stale-entry guard. Without
if (nodeDist > dist[node]) continue;, the lazy heap re-expands nodes through outdated distances. The answer often still comes out right, but you do redundant work — and if you also track avisitedset incorrectly, you can lock a node at the wrong distance. - Marking a node finalized when you push it, not when you pop it. A node's distance can improve while it sits in the heap (that's what Pop 2 → Pop 3 shows). Only the pop is authoritative.
- Initializing
dist[src]to something other than 0. The whole propagation is seeded by that single zero; forget it and every distance staysInfinity. - Assuming fewest hops means cheapest. In the example,
0 → 1is one hop but costs 4, while the two-hop0 → 2 → 1costs 3. Hop count and cost are unrelated once weights differ.
Where this pattern shows up next
Dijkstra is the weighted member of a family of graph traversals. These build the neighboring intuitions:
- Find if Path Exists in Graph — reachability with a plain BFS/DFS, the unweighted skeleton Dijkstra generalizes.
- All Paths From Source to Target — enumerating every route on a DAG, the brute-force side of path problems.
- Max Area of Island — flood-fill traversal on a grid, another exhaustive-exploration cousin.
- Redundant Connection — union-find over edges, the go-to tool when the question is about connectivity rather than distance.
You can also step through Dijkstra's algorithm interactively to watch the min-heap reorder and each edge relax, one operation at a time.
FAQ
Why does Dijkstra's algorithm require non-negative edge weights?
The algorithm finalizes a node's distance the instant it pops off the heap, trusting that no cheaper path can arrive afterward. That trust holds only when edges are non-negative — every remaining path is at least as long as the one just extracted. A negative edge could create a later, cheaper route into an already-locked node, and Dijkstra never re-examines locked nodes, so it would return a wrong answer. Graphs with negative weights need Bellman-Ford instead.
What is the time complexity of Dijkstra's algorithm?
With a binary min-heap it's O((V + E) log V), where V is the number of nodes and E the number of edges. Each edge relaxation can push one pair onto the heap, so there are up to E push/pop operations, and each costs O(log V). The simpler version that linear-scans for the minimum node is O(V²), which is faster only on dense graphs where E approaches V².
What are stale entries in the min-heap and why do we skip them?
This implementation never updates or removes old heap entries. When a shorter path to a node is found, it pushes a new, smaller [dist, node] pair and leaves the larger one behind. So the same node can sit in the heap multiple times at different distances. When an outdated pair eventually pops, its distance is larger than the best recorded dist[node], and the guard if (nodeDist > dist[node]) continue; discards it so the node isn't re-processed with wrong data.
How is Dijkstra different from BFS?
BFS finds shortest paths by hop count and assumes every edge costs 1, using a plain FIFO queue. Dijkstra handles arbitrary non-negative weights by replacing that queue with a priority queue ordered by total distance, so it always expands the globally closest node rather than the one added earliest. On an unweighted graph the two produce identical results — Dijkstra just carries the extra machinery to handle weights BFS can't.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.