Shortest Paths: Dijkstra

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Dijkstra's algorithm

Loading interactive demo…

Waypoints joined by weighted edges, the weights their lengths. The nearest unsettled node comes off a heap and is settled, its distance final; each edge out of it is relaxed, and a neighbour whose distance improves is pushed with the new distance. An entry a shorter route has overtaken is stale when it surfaces and is skipped. The search stops when the goal is settled, or runs on.Take the tour, or press and explore. Legend:

The panel beside the stage is the real Dijkstra class from the published library executing in your browser, with the current line highlighted.

The start, and the shortest path once the goal is settled.
The goal.
Settled nodes, labelled with their final distance, and the parent edges that reached them.
Nodes on the heap, hollow, labelled with their tentative distance.
The node being settled or the edge being relaxed.

settled counts the nodes with final distances, heapthe entries waiting, distance the last settled node's,to goal the goal's once it is settled. The strip shows the settled distances in order: they never decrease. Tap a waypoint to move the start or the goal.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The invariant. Keep a tentative distance $d(v)$ for every node, $0$ at the start and $\infty$ elsewhere, and a settled set $S$ . The claim: for every node in $S$ , $d(v)$ is the true shortest distance. It holds at the start, and it survives settling the unsettled node $u$ with the smallest $d(u)$ : any path from the start to $u$ leaves $S$ somewhere along an edge $(x, y)$ with $x \in S$ , and its length is at least $d(x) + w(x, y) \ge d(y) \ge d(u)$ , since $y$ was relaxed when $x$ was settled and $u$ has the smallest tentative distance. No path is shorter than $d(u)$ , so $u$ is settled correctly.

Relaxation. Settling $u$ offers each neighbour $v$ the route through $u$ : if $d(u) + w(u, v) < d(v)$ , take it, record $u$ as the parent, and push $v$ with the new distance. The parents form the shortest-path tree; following them back from the goal gives the path.

The heap, and stale entries. The nearest unsettled node must be found quickly, so the tentative distances live in a min-heap. A node whose distance improves is pushed again rather than moved; the older entry surfaces later, finds the node settled, and is skipped. That is lazy deletion, simpler than decrease-key and the same order of work: $O((V + E) \log V)$ with a binary heap.

Why the strip never falls. Settled distances come off the heap in non-decreasing order, which is the invariant seen from the side. It is also why stopping when the goal is settled is safe: everything still on the heap is at least as far.

Negative edges. The proof needs $w(x, y) \ge 0$ ; a negative edge could make a route that leaves $S$ come back shorter, and a settled distance would be wrong. Bellman-Ford relaxes every edge $V - 1$ times and pays for the generality. Edges: an unreachable node keeps $d = \infty$ and never settles; a start equal to the goal settles once and stops.

The algorithm was designed to show off a new computer. Edsger Dijkstra, a programmer at the Mathematical Centre in Amsterdam, wanted a problem a general audience would follow when the ARMAC was demonstrated, and chose the shortest way between two of sixty-four Dutch cities. He worked out the method at a cafe table in about twenty minutes and did not publish it for three years. It is still the way a satnav, a router, and a game character find the cheapest route, and the heap that keeps its nearest node at hand is the data structure that makes it fast.

1956Edsger W. Dijkstra - Designs the algorithm at a cafe in Amsterdam in about twenty minutes, to demonstrate the newly built ARMAC computer on a simplified map of 64 Dutch cities.source
1959Edsger W. Dijkstra - Publishes it as 'A note on two problems in connexion with graphs' in Numerische Mathematik, three years after conceiving it.source
1984Michael Fredman and Robert Tarjan - Introduce the Fibonacci heap, which brings the running time to E plus V log V, the fastest known for general graphs with non-negative weights.source

Used today

Routing - Link-state routing protocols run it on the network map at every router; satnavs run it, or A* on top of it, on the road graph.
Games - The cheapest route across a weighted grid or a nav mesh, and the ground A* stands on.
Networks of every kind - Flight connections, dependency costs, and pipeline latencies are shortest-path questions on a weighted graph.

nodes12

radius3.0

start noden0

goal noden11

a tap moves

exit

settled: 12 of 12
heap: 0
distance: 8.3
to goal: 8.3

dijkstra.ts

import type { Tracer } from "../trace";import { BinaryHeap } from "./binary-heap";import type { AdjacencyGraph } from "./graph";export interface DijkstraResult {  /** Shortest distance from the start to each node; Infinity where unreached. */  distance: number[];  /** Each node's predecessor on its shortest path; -1 for the start and the unreached. */  parent: number[];  /** Nodes in the order they were settled. */  settled: number[];  /** The shortest path to the goal, when one was given and reached; else empty. */  path: number[];}interface Entry {  node: number;  distance: number;}/** * Dijkstra's shortest paths: settle the nearest unsettled node, relax * its edges, repeat. A binary heap of (node, tentative distance) * entries picks the nearest; a node pushed again with a better distance * leaves a stale entry behind, skipped when it surfaces. A settled * distance is final because every other route leaves the settled set * along an edge of non-negative weight. Stops early once the goal, if * given and `stopAtGoal` is set, is settled; otherwise every reachable * node is settled and the goal only marks its settle event. * * Time: O((V + E) log V). Space: O(V + E). */export class Dijkstra {  constructor(    readonly graph: AdjacencyGraph,    private readonly tracer?: Tracer,  ) {}  run(start: number, goal = -1, stopAtGoal = true): DijkstraResult {    const n = this.graph.nodeCount;    if (!Number.isInteger(start) || start < 0 || start >= n) throw new RangeError(`start ${start} is not a node`);    if (goal >= n || !Number.isInteger(goal)) throw new RangeError(`goal ${goal} is not a node`);    const distance: number[] = Array.from({ length: n }, () => Infinity);    const parent: number[] = Array.from({ length: n }, () => -1);    const done: boolean[] = Array.from({ length: n }, () => false);    const isSettled: boolean[] = Array.from({ length: n }, () => false);    const settled: number[] = [];    const heap = new BinaryHeap<Entry>((e) => e.distance);    const nearestFirst = new BinaryHeap<Entry>((e) => e.distance);    distance[start] = 0;    heap.push({ node: start, distance: 0 });    nearestFirst.push({ node: start, distance: 0 });    while (heap.size > 0) {    while (nearestFirst.size > 0) {      const entry = heap.pop()!;      const heapEntry = nearestFirst.pop()!;      if (done[entry.node]) {      if (isSettled[heapEntry.node]) {        // A better route reached this node after the entry was pushed; the entry is stale.        // ▸ an entry pushed before a better route arrived: skip it        this.tracer?.emit("stale", { node: entry.node, distance: entry.distance, best: distance[entry.node] });        this.tracer?.emit("stale", { node: heapEntry.node, distance: heapEntry.distance, best: distance[heapEntry.node] });        continue;      }      done[entry.node] = true;      isSettled[heapEntry.node] = true;      settled.push(entry.node);      settled.push(heapEntry.node);      // ▸ the nearest unsettled node: its distance is final from here on      this.tracer?.emit("settle", { node: entry.node, distance: entry.distance, order: settled.length, goal: entry.node === goal });      this.tracer?.emit("settle", { node: heapEntry.node, distance: heapEntry.distance, order: settled.length, goal: heapEntry.node === goal });      if (entry.node === goal && stopAtGoal) break;      if (heapEntry.node === goal && stopAtGoal) break;      for (const { to, weight } of this.graph.neighbors(entry.node)) {      for (const { to, weight } of this.graph.neighbors(heapEntry.node)) {        if (done[to]) continue;        if (isSettled[to]) continue;        const old = distance[to]!;        const candidate = entry.distance + weight;        const candidate = heapEntry.distance + weight;        const improved = candidate < old;        // ▸ would going through this node shorten the way to its neighbour?        this.tracer?.emit("relax", { from: entry.node, to, weight, old: Number.isFinite(old) ? old : null, new: candidate, improved });        this.tracer?.emit("relax", { from: heapEntry.node, to, weight, old: Number.isFinite(old) ? old : null, new: candidate, improved });        if (!improved) continue;        distance[to] = candidate;        parent[to] = entry.node;        parent[to] = heapEntry.node;        heap.push({ node: to, distance: candidate });        nearestFirst.push({ node: to, distance: candidate });        // ▸ a shorter distance: onto the heap it goes        this.tracer?.emit("push", { node: to, distance: candidate, heap: heap.toArray().map((e) => e.node) });        this.tracer?.emit("push", { node: to, distance: candidate, nearestFirst: nearestFirst.toArray().map((e) => e.node) });      }    }    const path: number[] = [];    if (goal >= 0 && done[goal]) {    if (goal >= 0 && isSettled[goal]) {      for (let node = goal; node !== -1; node = parent[node]!) path.unshift(node);    }    return { distance, parent, settled, path };  }}

settled =: 12
to goal =: 8.3
path =: n0 n9 n10 n3 n11

12 nodes settled; the goal is 8.3 from the start along n0 n9 n10 n3 n11.

import type { Tracer } from "../trace";import { BinaryHeap } from "./binary-heap";import type { AdjacencyGraph } from "./graph";export interface DijkstraResult { /** Shortest distance from the start to each node; Infinity where unreached. */ distance: number[]; /** Each node's predecessor on its shortest path; -1 for the start and the unreached. */ parent: number[]; /** Nodes in the order they were settled. */ settled: number[]; /** The shortest path to the goal, when one was given and reached; else empty. */ path: number[];}interface Entry { node: number; distance: number;}/** * Dijkstra's shortest paths: settle the nearest unsettled node, relax * its edges, repeat. A binary heap of (node, tentative distance) * entries picks the nearest; a node pushed again with a better distance * leaves a stale entry behind, skipped when it surfaces. A settled * distance is final because every other route leaves the settled set * along an edge of non-negative weight. Stops early once the goal, if * given and `stopAtGoal` is set, is settled; otherwise every reachable * node is settled and the goal only marks its settle event. * * Time: O((V + E) log V). Space: O(V + E). */export class Dijkstra { constructor( readonly graph: AdjacencyGraph, private readonly tracer?: Tracer, ) {} run(start: number, goal = -1, stopAtGoal = true): DijkstraResult { const n = this.graph.nodeCount; if (!Number.isInteger(start) || start < 0 || start >= n) throw new RangeError(`start ${start} is not a node`); if (goal >= n || !Number.isInteger(goal)) throw new RangeError(`goal ${goal} is not a node`); const distance: number[] = Array.from({ length: n }, () => Infinity); const parent: number[] = Array.from({ length: n }, () => -1); const done: boolean[] = Array.from({ length: n }, () => false); const isSettled: boolean[] = Array.from({ length: n }, () => false); const settled: number[] = []; const heap = new BinaryHeap<Entry>((e) => e.distance); const nearestFirst = new BinaryHeap<Entry>((e) => e.distance); distance[start] = 0; heap.push({ node: start, distance: 0 }); nearestFirst.push({ node: start, distance: 0 }); while (heap.size > 0) { while (nearestFirst.size > 0) { const entry = heap.pop()!; const heapEntry = nearestFirst.pop()!; if (done[entry.node]) { if (isSettled[heapEntry.node]) { // A better route reached this node after the entry was pushed; the entry is stale. // ▸ an entry pushed before a better route arrived: skip it this.tracer?.emit("stale", { node: entry.node, distance: entry.distance, best: distance[entry.node] }); this.tracer?.emit("stale", { node: heapEntry.node, distance: heapEntry.distance, best: distance[heapEntry.node] }); continue; } done[entry.node] = true; isSettled[heapEntry.node] = true; settled.push(entry.node); settled.push(heapEntry.node); // ▸ the nearest unsettled node: its distance is final from here on this.tracer?.emit("settle", { node: entry.node, distance: entry.distance, order: settled.length, goal: entry.node === goal }); this.tracer?.emit("settle", { node: heapEntry.node, distance: heapEntry.distance, order: settled.length, goal: heapEntry.node === goal }); if (entry.node === goal && stopAtGoal) break; if (heapEntry.node === goal && stopAtGoal) break; for (const { to, weight } of this.graph.neighbors(entry.node)) { for (const { to, weight } of this.graph.neighbors(heapEntry.node)) { if (done[to]) continue; if (isSettled[to]) continue; const old = distance[to]!; const candidate = entry.distance + weight; const candidate = heapEntry.distance + weight; const improved = candidate < old; // ▸ would going through this node shorten the way to its neighbour? this.tracer?.emit("relax", { from: entry.node, to, weight, old: Number.isFinite(old) ? old : null, new: candidate, improved }); this.tracer?.emit("relax", { from: heapEntry.node, to, weight, old: Number.isFinite(old) ? old : null, new: candidate, improved }); if (!improved) continue; distance[to] = candidate; parent[to] = entry.node; parent[to] = heapEntry.node; heap.push({ node: to, distance: candidate }); nearestFirst.push({ node: to, distance: candidate }); // ▸ a shorter distance: onto the heap it goes this.tracer?.emit("push", { node: to, distance: candidate, heap: heap.toArray().map((e) => e.node) }); this.tracer?.emit("push", { node: to, distance: candidate, nearestFirst: nearestFirst.toArray().map((e) => e.node) }); } } const path: number[] = []; if (goal >= 0 && done[goal]) { if (goal >= 0 && isSettled[goal]) { for (let node = goal; node !== -1; node = parent[node]!) path.unshift(node); } return { distance, parent, settled, path }; }}