Dijkstra's algorithm
Keep a best-known distance for every node. Again and again, take the closest node not yet settled: no route through anything further away can beat it, so its distance is final. Then see whether going through it shortens the route to any neighbour.
priority queue: smallest distance first
Find the shortest route from A to every node, where each edge has a length.
1function dijkstra(adj, start) {2 const dist = new Array(adj.length).fill(Infinity);3 dist[start] = 0;4 const pq = new MinHeap([[0, start]]);5 while (pq.size > 0) {6 const [d, u] = pq.pop();7 if (d > dist[u]) continue;8 for (const [v, w] of adj[u]) {9 if (d + w < dist[v]) {10 dist[v] = d + w;11 pq.push([dist[v], v]);12 }13 }14 }15 return dist;16}17// MinHeap is any binary heap of [distance, node] pairs, as on the Binary heap page.Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | E log V | with a binary heap as the priority queue |
| average | E log V | any graph with non-negative weights |
| worst | E log V | each edge can add one queue entry |
| space | V + E | distances, plus out-of-date queue entries |
Where it breaks
- Negative weights break it. Settling a node assumes no later route can be shorter. A negative edge found later can undo that, and Dijkstra never goes back. Use Bellman-Ford when weights can be negative.
- Fewest edges is not shortest. Pick Detour wins: A to B directly costs 10, but A, C, D, B costs 3. Dijkstra finds it; breadth-first search, counting hops, would not.
- Out-of-date queue entries. This version never updates entries in the queue; it just adds a new, shorter one and skips the stale one when it comes out. That is simpler than a heap with decrease-key, and why the queue can hold more than V entries.