Dijkstra's Shortest-Path Algorithm

You type a destination into a satnav and, in a heartbeat, it draws the quickest route across a whole country of roads. How? Behind the map is a weighted graph: the junctions are vertices, the roads are edges, and each edge carries a weight — the distance, or the time, to drive it. The question "what is the fastest way from here to there?" becomes: which route through the graph has the smallest total weight?

In 1956 the Dutch computer scientist Edsger Dijkstra worked out a beautifully simple method to answer exactly this, and it is still the beating heart of route-planners, network routers and game AI today. Given a start vertex, Dijkstra's algorithm finds the shortest (lowest-total-weight) path from that start to every other vertex — not just one destination, but all of them at once.

You already know how to explore a graph blindly with a breadth-first or depth-first traversal. Those visit vertices in an order fixed by the shape of the graph. Dijkstra is cleverer: it lets the weights decide the order, always reaching for the nearest place it hasn't been yet.

The big idea: keep a tentative distance to everywhere

Imagine standing at the start with no idea how far anything is. Dijkstra keeps a running guess — a tentative distance — of the shortest way to reach each vertex found so far. At the beginning it knows almost nothing, so it makes the most cautious guesses possible:

Then it improves those guesses, over and over, with a single repeated move:

That third step is the whole trick, and it has a name: relaxing an edge. To relax the edge from a vertex u to a neighbour v means asking "is the path to v through u shorter than the best I'd found before?" — and if so, taking it:

\text{if } \; d(u) + w(u, v) \;<\; d(v) \quad\Longrightarrow\quad d(v) \leftarrow d(u) + w(u, v).

The magic is why a visited vertex's distance is safe to freeze. Because we always expand the closest unvisited vertex, and all weights are positive, no route we discover later can possibly sneak in and beat it — any other path would have to pass through a vertex that is already further away. We'll come back to that "all weights positive" assumption; it matters a lot.

Watch it work, step by step

Here is a small weighted graph of five places, A to E, with the distance written on every road. We'll run Dijkstra from A. Step through it: each step finalises the closest remaining vertex (its shortest distance appears in a badge) and highlights the road used to reach it. Watch how B is a red herring — the direct road A\!-\!B costs 4, but a sneaky detour turns out shorter.

Follow the numbers. From A (distance 0) we can reach C for 2 and B for 4. The closest unvisited vertex is C at 2, so we finalise it. Now — and this is the clever bit — from C we can hop to B for just 1 more, a total of 2 + 1 = 3. That beats the direct road's 4, so B's tentative distance drops from 4 to 3. The shortest path isn't always the most direct edge!

Carrying on, D is reached best via B (3 + 5 = 8, beating the direct C\!-\!D of 2 + 8 = 10), and finally E via D for 8 + 3 = 11. The finished shortest path from A to E runs A \to C \to B \to D \to E, total 11.

The trace, written as a table

A-level questions often ask you to keep a table of tentative distances, crossing out an old value when a shorter one is found. Here is the same run as a trace — each row is one iteration, and an arrow 4 \to 3 marks a value that got relaxed to something smaller:

Visit A B C D E ----- --- --- --- --- --- start 0 ∞ ∞ ∞ ∞ A (0) — 4 2 ∞ ∞ C (2) — 4 → 3 — 10 ∞ B (3) — — — 10 → 8 ∞ D (8) — — — — 11 E (11) — — — — — Final shortest distances from A: A=0 B=3 C=2 D=8 E=11

Read down the "Visit" column: the vertices are finalised in order of increasing distance — 0, 2, 3, 8, 11 — never in the order they happen to be listed. That ordering is the engine of the whole algorithm.

Dijkstra in TypeScript

Let's turn the recipe into code. We store the graph as an adjacency list where each entry is a weighted edge — a neighbour together with the cost to reach it. Then dijkstra follows the four steps exactly: initialise distances, then repeatedly pick the closest unvisited vertex and relax its neighbours. Press Run and read the shortest distances it prints:

type Edge = { to: string; weight: number }; // A weighted, undirected adjacency list: vertex → list of weighted edges. const graph = new Map<string, Edge[]>(); function addEdge(a: string, b: string, w: number): void { if (!graph.has(a)) graph.set(a, []); if (!graph.has(b)) graph.set(b, []); graph.get(a)!.push({ to: b, weight: w }); graph.get(b)!.push({ to: a, weight: w }); // both ways: the graph is undirected } addEdge("A", "B", 4); addEdge("A", "C", 2); addEdge("B", "C", 1); addEdge("B", "D", 5); addEdge("C", "D", 8); addEdge("D", "E", 3); function dijkstra(start: string): Map<string, number> { const dist = new Map<string, number>(); const visited = new Set<string>(); for (const v of graph.keys()) dist.set(v, Infinity); // everyone starts at ∞... dist.set(start, 0); // ...except the start, at 0 while (visited.size < graph.size) { // 1) pick the UNVISITED vertex with the smallest tentative distance let u: string | null = null; let best = Infinity; for (const [v, d] of dist) { if (!visited.has(v) && d < best) { best = d; u = v; } } if (u === null) break; // any leftover vertices are unreachable visited.add(u); // its distance is now final // 2) relax every neighbour: is the path VIA u shorter than what we had? for (const edge of graph.get(u)!) { const alt = dist.get(u)! + edge.weight; if (alt < dist.get(edge.to)!) dist.set(edge.to, alt); } } return dist; } const distances = dijkstra("A"); for (const [v, d] of distances) { console.log("shortest A → " + v + " = " + d); }

The output matches our table exactly: A\!=\!0, B\!=\!3, C\!=\!2, D\!=\!8, E\!=\!11. Try adding a new road with addEdge, or a whole new vertex, and re-run — Dijkstra re-plans instantly, just like your satnav when you miss a turn.

Our version scans every vertex each time it hunts for the closest unvisited one. For a graph of V vertices and E edges that costs about V^2 work — fine for a few dozen towns, slow for a whole road network. Professional implementations keep the tentative distances in a priority queue (a min-heap), which serves up the smallest one almost for free. That drops the cost to about (V + E)\log V — the difference between a satnav that thinks for a millisecond and one that thinks for a minute. The logic is identical; only the "find-the-minimum" step gets faster.

Two mistakes trip people up, and both come from forgetting why Dijkstra is allowed to freeze a vertex forever the moment it visits it.

1. It assumes every edge weight is non-negative. Dijkstra's guarantee — "the closest unvisited vertex can never be improved later" — relies on extra steps only ever adding distance. Put a negative weight in the graph and that promise breaks: a later, longer-looking route could dip below what you already finalised, and Dijkstra will happily report a wrong answer, because it never looks back at a visited vertex. For graphs with negative edges you need a different algorithm (the Bellman–Ford algorithm). Happily, distances and travel times are never negative, which is why Dijkstra rules the roads.

2. Always expand the closest unvisited vertex — not the order you happened to see them. It is tempting to process vertices in the order they first turned up, or the order they sit in your list. That's breadth-first thinking, and on a weighted graph it gives the wrong shortest paths. Dijkstra specifically pulls out the smallest tentative distance every time; that ordering is not an optional detail, it is the reason the algorithm is correct.

A related idea worth knowing: if you only care about one destination and can estimate how far each vertex is from it (say, straight-line distance on a map), you can steer the search toward the goal instead of spreading out evenly. That extension is called A* search — Dijkstra plus a heuristic — and it's what most game and map engines actually run.