Dijkstra's Algorithm

The 10-second versionCopy Anchor Link

Hand me a graph where every edge has a non-negative cost, plus one starting node, and Dijkstra tells you the cheapest total cost to reach every other node — and the path that gets you there. The whole trick is an ordering rule: always expand the cheapest-so-far node you haven't finished yet, using a priority queue to hand it over in O(log n). Because a later route through a negative edge could beat a node you already "finished," the non-negative assumption is doing real work — and it is exactly what lets Dijkstra finalize a node and never look back. It is breadth-first search that finally learned about weights.

Why this existedCopy Anchor Link

The problem is as old as roads: what is the cheapest way to get from here to there? By the 1950s the question had moved from maps to networks — telephone trunks, pipelines, scheduling — but the answer still had to be ground out by hand or by brute force.

In 1956 the Mathematical Centre in Amsterdam had a brand-new machine called ARMAC, and Edsger W. Dijkstra wanted a demo for it. Not a numerical one — something a non-programmer could look at and immediately judge. The shortest route between two cities was perfect. He also had a hard constraint that shaped the entire design: keep it as simple as it could possibly be, because the machine was slow and the audience was skeptical.

He designed it in about twenty minutes, sitting at a café terrace in Amsterdam, with no pencil and no paper — he even said he wanted "the simplest thing that worked." He later told the story himself. The algorithm was finally published in 1959 in Numerische Mathematik, under the wonderfully dry title "A note on two problems in connexion with graphs."

Why it mattered: it turned "find the cheapest route" from an exponential search into a near-linear sweep. Every GPS turn, every packet route, every game AI that walks a character from A to B is standing on that twenty-minute café idea.

Inside the inventor's headCopy Anchor Link

The obvious first idea is breadth-first search: explore outward by hops. That is exactly right when every edge costs the same, because then the fewest hops is the cheapest path. The trap is that it collapses the moment edges have different weights.

So he keeps a number next to every node — the best known cost from the source — and always reaches for the smallest one. But why is it safe to finalize a node the moment you pull it out? Here is the load-bearing argument, and it is worth sitting with.

Picture the set of nodes you have already finalized. When you pull out the unfinished node u with the smallest tentative cost d, any route you have not discovered yet must at some point jump from a finalized node x to an unfinished node y, crossing the "cut" between the two groups. That jump alone costs at least dist(x) + w(x, y). Because u has the smallest tentative cost among unfinished nodes, d is no larger than the cost of that jump, which is no larger than the whole route. So no undiscovered route can ever beat d. The node is truly done — that is the entire "why is greedy safe?" proof, and it fits in a paragraph.

The catch: that argument leans entirely on weights being non-negative. Add even one negative edge and a "finished" node can suddenly get cheaper. That single assumption is the whole ballgame, and it is exactly why Bellman-Ford had to be invented separately.

The final approachCopy Anchor Link

The algorithmCopy Anchor Link

1. Set dist[source] = 0 and every other dist to infinity. Push the source.
2. Pop the node u with the smallest tentative cost. If the entry is stale, skip it and pop again.
3. Finalize u. For each neighbor v with edge weight w: if dist[u] + w is smaller than dist[v], relax the edge — update dist[v] and push it.
4. Repeat until the queue is empty.

The invariantsCopy Anchor Link

• Finalized is final. Once a node is popped and settled, its dist is the true shortest distance. It will never be updated again.
• Tentative is best-known. For every unfinished node, dist is the best cost found over paths whose interior nodes are already finalized.
• Monotone growth. The sequence of finalized distances never decreases, which is precisely what makes "pop the smallest" safe.

Relaxation, step by stepCopy Anchor Link

Take four nodes — S, A, B, C — with directed edges S→A = 4, S→B = 1, B→A = 2, A→C = 5, B→C = 8. Watch the two improvements land:

Final distances: S = 0, B = 1, A = 3, C = 8. The two relaxations that beat an existing value are the heart of it — a shorter route surfaced after the node was first reached, and Dijkstra happily rewrote it because the node had not yet been finalized.

It in codeCopy Anchor Link

class MinHeap {  constructor() { this.a = []; }  get size() { return this.a.length; }  push(item) {    const a = this.a; a.push(item);    let i = a.length - 1;    while (i > 0) {      const p = (i - 1) >> 1;      if (a[p][0] <= a[i][0]) break;      [a[p], a[i]] = [a[i], a[p]];      i = p;    }  }  pop() {    const a = this.a, top = a[0], last = a.pop();    if (a.length) {      a[0] = last;      let i = 0;      for (;;) {        const l = 2 * i + 1, r = l + 1;        let s = i;        if (l < a.length && a[l][0] < a[s][0]) s = l;        if (r < a.length && a[r][0] < a[s][0]) s = r;        if (s === i) break;        [a[s], a[i]] = [a[i], a[s]];        i = s;      }    }    return top;  }}function dijkstra(adj, src) {  const dist = new Array(adj.length).fill(Infinity);  dist[src] = 0;  const pq = new MinHeap();  pq.push([0, src]);                         // [cost, node]  while (pq.size) {    const [d, u] = pq.pop();    if (d > dist[u]) continue;               // stale entry    for (const [v, w] of adj[u]) {      if (d + w < dist[v]) {                 // relax the edge        dist[v] = d + w;        pq.push([dist[v], v]);      }    }  }  return dist;}

ComplexityCopy Anchor Link

The heap is not optional once your graph gets big: the simple "scan every node to find the minimum" version is O(V²), which is fine only for dense graphs where E ≈ V² anyway. For a road network with millions of nodes and a handful of edges each, the heap is what keeps routing interactive.

Where you meet it todayCopy Anchor Link

• Maps and navigation. Google Maps, OSRM, and every routing engine run Dijkstra or a close variant (A*, contraction hierarchies) over the road graph, where each edge's weight is travel time, not distance.
• Network routing. OSPF and IS-IS, the protocols that route packets inside an autonomous system, each router runs Dijkstra over the link-state topology to fill its forwarding table.
• Game AI and robotics. Grid and navmesh pathfinding is Dijkstra when moves have varying cost, and the exact cost model behind every "click to move" command.
• Social and dependency graphs. "Fewest hops" variants show up in recommendation and dependency analyses whenever edges carry weights.

Real pathfinders stop early: the moment the destination is popped, its distance is final, so there is no reason to finish sweeping the rest of the graph.

const [d, u] = pq.pop();if (u === target) return d;   // goal settled -> its distance is finalif (d > dist[u]) continue;    // otherwise skip a stale entry

RecapCopy Anchor Link

• Dijkstra is breadth-first search plus a priority queue that always expands the cheapest-so-far node.
• It is correct because edge weights are non-negative: a settled node can never be improved later.
• Relaxation — if dist[u] + w < dist[v] — is the atomic move; stale heap entries are simply skipped.
• With a binary heap it runs in O((V + E) log V) time and O(V + E) space.
• Negative edges break the proof entirely — that job belongs to Bellman-Ford.

Next up: Bellman-Ford — the same goal, but willing to pay extra to tolerate negative edges.