What you're seeing
Same grid as breadth-first search, but now every cell costs something to enter — think hills and mud, lighter cells being more expensive. Dijkstra repeatedly settles the unfinished cell with the smallest distance-so-far, then relaxes its neighbors. Because it always grows the cheapest frontier, the blue settled region doesn't spread in even rings like BFS — it bulges through cheap valleys and stalls against expensive ridges. When the target is settled, its distance is the minimum possible total cost, and the green trail is the route that achieves it — which may be longer in cells than a straight shot, but cheaper in total.
The rule
dijkstra(source):
dist[source] = 0; everything else = ∞
PQ = all nodes, keyed by dist
while PQ not empty:
u = PQ.extract_min() # closest unfinished node
for each neighbor v of u:
if dist[u] + weight(v) < dist[v]:
dist[v] = dist[u] + weight(v) # relax
parent[v] = u
A priority queue (a binary heap) replaces BFS's plain FIFO queue — that's the one change that turns "fewest hops" into "cheapest cost."
The invariant
When a node is settled (extracted from the priority queue as the current minimum), its recorded distance is its true shortest-path cost — final, never to improve. Why: suppose u is being extracted with distance d, and imagine some shorter path to u existed. That path leaves the settled set somewhere, at a first unsettled node x; the prefix to x already costs at least dist[x] ≥ d (or x would have been extracted before u), and the rest of the path adds only non-negative weight — so it can't total less than d. Contradiction. The whole argument hinges on weights being ≥ 0: with a negative edge a "finished" node could later be cheapened, and the invariant — and Dijkstra — break (that's when you need Bellman–Ford).
The cost
Each node is extracted once (V heap pops) and each edge can trigger a decrease-key (E updates); with a binary heap that's O((V+E)\,\log V). A Fibonacci heap improves it to O(E + V\,\log V) in theory, though binary (or pairing) heaps usually win in practice. When all weights are equal, Dijkstra degenerates to exactly BFS — the priority queue just reproduces FIFO order. (This demo uses a simple O(V²) scan for clarity; the heap version is what ships.)
In the wild
Dijkstra is the canonical shortest-path algorithm: road and transit routing (as the base under A* and, at continental scale, contraction hierarchies), network routing protocols (OSPF / IS-IS compute least-cost paths with it), robot motion planning, and anywhere a graph has non-negative costs. Its descendants specialize it: A* adds a goal-directed heuristic to explore far fewer cells, and modern map services precompute shortcuts so a continental query answers in microseconds. For graphs with negative edges, Bellman–Ford takes over; for all-pairs, Floyd–Warshall.
Try this
Turn Terrain roughness up and watch the settled region stop being round — it races down cheap corridors and avoids the bright expensive cells, and the green path visibly detours around costly terrain. Compare with BFS on the same layout: BFS counts cells, Dijkstra counts cost, and the two pick different routes.
References
- Dijkstra, E. W. "A note on two problems in connexion with graphs." Numerische Mathematik 1:269–271, 1959. The original.
- Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §22.3 — Dijkstra, the priority-queue implementation, and the non-negative-weight invariant. MIT Press, 2022.
- Fredman, M. & Tarjan, R. "Fibonacci heaps and their uses in improved network optimization algorithms." JACM 34(3), 1987 — the O(E + V log V) bound.
- Sedgewick & Wayne. Algorithms, 4th ed., §4.4 (Shortest Paths). algs4.cs.princeton.edu/44sp.