Dijkstra's Algorithm, and the Four Places It Quietly Breaks

Three nodes are enough to make a breadth-first search lie to you.

BFS from A reaches B in one hop and reports a cost of 5. The actual cheapest route is A -> C -> B at 2. BFS is not broken — it answers "fewest edges", and on an unweighted graph fewest edges is the same question as cheapest path. The moment edges carry a cost, they stop being the same question.

Dijkstra's algorithm answers the cheapest-path question with one rule: always settle the cheapest unsettled node next. Everything else in this post — the heap, the stale-entry check, the early exit — is machinery for making that one rule fast, and each piece of that machinery has a specific way of going wrong.

I wrote the implementation below, then spent most of the time trying to break it. Everything here comes from running it, not from reading it.

Your min query is your complexity class

The rule "settle the cheapest unsettled node next" is a min query in a loop, and the data structure you pick for it is your complexity class. JavaScript has no built-in priority queue, so this is code you write.

The tempting shortcut is a plain array plus sort() on every iteration, or a linear scan for the minimum. Both work. Both also turn an O(E log V) algorithm into something quadratic while you keep writing log V in the comment. So: a real binary heap, about 50 lines.

type Edge = { to: number; weight: number };
type WeightedGraph = Edge[][];
 
/** Binary min-heap keyed on `distance`. Entries are (node, distance) pairs. */
class MinHeap {
  private items: { node: number; distance: number }[] = [];
 
  get size(): number {
    return this.items.length;
  }
 
  push(node: number, distance: number): void {
    this.items.push({ node, distance });
    this.siftUp(this.items.length - 1);
  }
 
  pop(): { node: number; distance: number } | undefined {
    if (this.items.length === 0) return undefined;
    const top = this.items[0];
    const last = this.items.pop()!;
    if (this.items.length > 0) {
      this.items[0] = last;
      this.siftDown(0);
    }
    return top;
  }
 
  private siftUp(i: number): void {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.items[parent].distance <= this.items[i].distance) break;
      this.swap(i, parent);
      i = parent;
    }
  }
 
  private siftDown(i: number): void {
    const n = this.items.length;
    for (;;) {
      const left = 2 * i + 1;
      const right = left + 1;
      let smallest = i;
      if (left < n && this.items[left].distance < this.items[smallest].distance) smallest = left;
      if (right < n && this.items[right].distance < this.items[smallest].distance) smallest = right;
      if (smallest === i) return;
      this.swap(i, smallest);
      i = smallest;
    }
  }
 
  private swap(i: number, j: number): void {
    const t = this.items[i];
    this.items[i] = this.items[j];
    this.items[j] = t;
  }
}

siftDown and pop are where the bugs live, and neither one announces itself.

siftDown has to compare against both children and descend into the smaller one. Check only the left child and the heap still pops something, still terminates, and still gives the right answer on the four-node example in every tutorial. I delete that comparison later in this post to see whether my tests catch it.

pop() on an empty heap has to leave the heap empty. The common version starts with if (this.items.length === 1) return this.items.pop() and then unconditionally does this.items[0] = this.items.pop()!. On an empty heap that assigns undefined into index 0, which grows length back to 1, so isEmpty() reports false forever and the caller's while loop never exits. The version above returns early instead.

decrease-key, and why you should not write it

Textbook Dijkstra keeps one heap entry per vertex and calls decreaseKey when it finds a cheaper route. To do that in logarithmic time you need a node-to-heap-index map maintained through every swap. It is real code, it is fiddly, and it buys you nothing at interview scale.

The alternative is lazy deletion: never update an entry, just push a second one. The heap now holds (B, 5) and (B, 2). It hands you (B, 2) first, you settle B, and when (B, 5) eventually surfaces you notice 5 > dist[B] and skip it. The heap can grow to E entries instead of V, and since E <= V * V, log E <= 2 log V — the asymptotic bound does not move.

If an article claims decreaseKey and then pushes duplicates, it is doing lazy deletion under another name.

The algorithm

type DijkstraResult = { dist: number[]; prev: (number | null)[]; pops: number };
 
function dijkstra(
  graph: WeightedGraph,
  source: number,
  target: number | null = null,
): DijkstraResult {
  const n = graph.length;
  const dist = new Array<number>(n).fill(Infinity);
  const prev = new Array<number | null>(n).fill(null);
  const pq = new MinHeap();
  let pops = 0;
 
  dist[source] = 0;
  pq.push(source, 0);
 
  for (;;) {
    const entry = pq.pop();
    if (entry === undefined) break;
    pops++;
 
    const { node: u, distance: d } = entry;
 
    // Stale entry: we already settled `u` on a cheaper path, so this copy
    // is a leftover from an earlier, worse relaxation. Drop it.
    if (d > dist[u]) continue;
 
    // `u` is settled. If it is the only node we care about, stop now — no
    // later pop can produce a smaller distance for it.
    if (u === target) break;
 
    for (const edge of graph[u]) {
      const candidate = d + edge.weight;
      if (candidate < dist[edge.to]) {
        dist[edge.to] = candidate;
        prev[edge.to] = u;
        pq.push(edge.to, candidate);
      }
    }
  }
 
  return { dist, prev, pops };
}
 
/** Shortest source->target path. `distance` is Infinity and `path` is [] when unreachable. */
function shortestPath(
  graph: WeightedGraph,
  source: number,
  target: number,
): { distance: number; path: number[] } {
  const n = graph.length;
  if (!Number.isInteger(source) || source < 0 || source >= n) {
    throw new RangeError(`source ${source} is not a node in a ${n}-node graph`);
  }
  if (!Number.isInteger(target) || target < 0 || target >= n) {
    throw new RangeError(`target ${target} is not a node in a ${n}-node graph`);
  }
 
  const { dist, prev } = dijkstra(graph, source, target);
  if (dist[target] === Infinity) return { distance: Infinity, path: [] };
 
  const path: number[] = [];
  for (let at: number | null = target; at !== null; at = prev[at]) path.push(at);
  path.reverse();
  return { distance: dist[target], path };
}

A few of those lines are decisions rather than transcription, so here is the defence.

Unreachable returns Infinity, not -1. A sentinel of -1 is a LeetCode output format, not an internal one: every caller has to remember to branch on it, and the day someone adds a variant with zero or negative weights it becomes a real distance. Infinity compares correctly against every real distance, which is why it is what the array starts out full of.

The range check is not defensive padding. Without it, an out-of-range target reads dist[target] as undefined, undefined === Infinity is false, so reconstruction runs — and the loop condition at !== null never sees null either, because prev[undefined] is undefined. I hit this by accident while writing the benchmarks: the process spun until path.push threw RangeError: Invalid array length, which is what a JS array does at 2^32 - 1 entries. A typo in an argument should not cost you four billion iterations.

dijkstra returns the whole dist array; shortestPath wraps it. LeetCode 743 (Network Delay Time) wants Math.max(...dist) over every node, which the early exit would sabotage. target defaults to null, which disables the early exit, so the all-targets case is the one you get by accident.

Here is the same trap as the graph at the top of the post, with one more node bolted on so the cheap detour has somewhere to lead. Node 0 reaches node 1 directly for 4, or for 3 by going through node 2 first. The target is node 3.

Every edge in that diagram is a line in the array below, in the same order:

const city: WeightedGraph = [
  [{ to: 1, weight: 4 }, { to: 2, weight: 1 }], // 0
  [{ to: 3, weight: 3 }],                        // 1
  [{ to: 1, weight: 2 }, { to: 3, weight: 6 }],  // 2
  [],                                            // 3
];
 
console.log(shortestPath(city, 0, 3));
// { distance: 6, path: [ 0, 2, 1, 3 ] }

Testing it against a judge that cannot be wrong

Tracing five steps by hand proves the algorithm works on one graph. I wanted the graphs I did not think of: self-loops, parallel edges with different weights, zero-weight edges, disconnected targets, a single node with no edges. So generate them randomly and check every answer against Floyd-Warshall, which is O(V^3) — too slow to ship, short enough to be obviously right.

const assert = (cond: boolean, msg: string): void => {
  if (!cond) throw new Error(msg);
};
 
/** O(V^3) oracle. Too slow to ship, fast enough to be the judge. */
function floydWarshall(graph: WeightedGraph): number[][] {
  const n = graph.length;
  const d = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)),
  );
  for (let u = 0; u < n; u++) {
    for (const e of graph[u]) d[u][e.to] = Math.min(d[u][e.to], e.weight);
  }
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
  return d;
}
 
function randomGraph(n: number): WeightedGraph {
  const g: WeightedGraph = Array.from({ length: n }, () => []);
  const density = Math.random();
  for (let u = 0; u < n; u++)
    for (let v = 0; v < n; v++) {
      // self-loops and parallel edges are deliberately allowed
      if (Math.random() < density) g[u].push({ to: v, weight: Math.floor(Math.random() * 11) });
      if (Math.random() < density * 0.2) g[u].push({ to: v, weight: Math.floor(Math.random() * 11) });
    }
  return g;
}
 
let graphs = 0;
let pairs = 0;
for (let t = 0; t < 4000; t++) {
  const n = 1 + Math.floor(Math.random() * 8);
  const g = randomGraph(n);
  const oracle = floydWarshall(g);
  graphs++;
  for (let s = 0; s < n; s++)
    for (let d = 0; d < n; d++) {
      pairs++;
      const { distance, path } = shortestPath(g, s, d);
      assert(distance === oracle[s][d], `dist ${s}->${d}: got ${distance}, oracle ${oracle[s][d]}`);
      assert(relaxWithFifoQueue(g, s)[d] === oracle[s][d], `fifo ${s}->${d} disagrees`);
      if (distance === Infinity) {
        assert(path.length === 0, "unreachable target must return an empty path");
        continue;
      }
      assert(path[0] === s && path[path.length - 1] === d, `path ${s}->${d} has wrong endpoints`);
      // The bug this catches: a prev[] chain that reconstructs a path whose
      // weight does not add up to the distance the function reported.
      let walked = 0;
      for (let i = 0; i + 1 < path.length; i++) {
        const options = g[path[i]].filter((e) => e.to === path[i + 1]);
        assert(options.length > 0, `path uses edge ${path[i]}->${path[i + 1]} that does not exist`);
        walked += Math.min(...options.map((e) => e.weight));
      }
      assert(walked === distance, `path weight ${walked} != reported distance ${distance}`);
    }
}
console.log(`ok: ${graphs} graphs, ${pairs} (source, target) pairs, 0 disagreements`);
// ok: 4000 graphs, 101563 (source, target) pairs, 0 disagreements
// (graphs are random, so the pair count moves a few percent per run; the zero does not)

That last assertion — reconstructed path weight equals reported distance — is the one worth stealing. A prev[] array is trivial to write and trivially wrong: it is correct only because prev[v] is always set to a node that was already settled, so dist[prev[v]] can never change afterwards and the sum telescopes. Nothing enforces that. When I changed one line to prev[edge.to] = source, the distances stayed perfect and only the path assertions failed — the edge-existence one first, the weight one on the graphs where the fabricated edge happened to exist anyway. Distance-only tests would have shipped it.

A second mutation, deleting the right-child comparison in siftDown so it only ever looks left, also failed within the first few graphs — on a distance assertion, not a path one. (Deleting the left comparison instead fails just as fast; neither half of that check is optional.) A third mutation — deleting the stale-entry check entirely — passed all 4,000 graphs, which is the correct result and the subject of the next section.

I also ran a wider sweep outside the article's harness: 2,000 sparse graphs with up to 40 nodes, 1,102,090 source-target pairs, checked against Bellman-Ford. Zero disagreements.

Where the milliseconds go

Everything below was measured on Node v22.22.3, arm64 Linux container, 4 cores, 4 GB RAM. Best of three runs. The graphs come from a seeded generator: a Hamiltonian cycle u -> (u + 1) mod V so every node is reachable, plus random extra edges to average out-degree 8 — except in the array-queue table, where the degree is 6 so the slow version finishes this decade. Every edge weight is a uniform integer in 1..100. Keep that one in view: it sets the size of one of the numbers below, and I show the sweep when I get there.

Does it grow like E log V?

Doubling V and E together should multiply the time by 2 * log(2V) / log(V), about 2.1 in this range. Observed: 2.08x to 2.96x. The normalised column drifts up 2.7x across a 60x size increase — far too slowly to be an extra log factor, and it flattens at the top end. That is the memory hierarchy, not the algorithm.

What Array.shift() costs. Here is the same relaxation loop with a FIFO array queue instead of a heap:

function relaxWithFifoQueue(graph: WeightedGraph, source: number): number[] {
  const dist = new Array<number>(graph.length).fill(Infinity);
  dist[source] = 0;
  const queue: [number, number][] = [[source, 0]];
 
  while (queue.length > 0) {
    const [u, d] = queue.shift()!; // O(queue.length), not O(1)
    if (d > dist[u]) continue;
    for (const edge of graph[u]) {
      const candidate = d + edge.weight;
      if (candidate < dist[edge.to]) {
        dist[edge.to] = candidate;
        queue.push([edge.to, candidate]);
      }
    }
  }
  return dist;
}

It returns correct distances — it is Bellman-Ford-Moore, and my differential test runs it on every graph alongside the heap version. It is just slow, in a way that gets worse:

The last two columns are computed from the unrounded timings, which is why they do not divide cleanly out of the millisecond column next to them. The heap stays between 2x and 3x per doubling all the way down. The array queue is flat until it is not: 2.2x, then 21.2x as the queue outgrows whatever V8 was doing cheaply, then 5x to 6x per doubling from there, because every shift() moves the rest of the queue. At 64,000 nodes it is 40x slower on identical input. If you write a linear scan or a sort() inside the loop and annotate it O((V + E) log V), this is the curve you are actually shipping.

What the stale-entry check is worth. Removing if (d > dist[u]) continue; changes no answers. It changes work. Here is the generator and the counter, so the numbers underneath are numbers you can get back rather than numbers you have to believe:

/** Seeded PRNG (mulberry32), so these are the same graphs on your machine as on mine. */
function mulberry32(a: number): () => number {
  return () => {
    a |= 0; a = (a + 0x6d2b79f5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
 
/** Hamiltonian cycle plus random chords. Weights uniform in 1..maxWeight. */
function benchGraph(V: number, deg: number, maxWeight: number, seed: number): WeightedGraph {
  const rnd = mulberry32(seed);
  const g: WeightedGraph = Array.from({ length: V }, () => []);
  for (let u = 0; u < V; u++) {
    g[u].push({ to: (u + 1) % V, weight: 1 + Math.floor(rnd() * maxWeight) });
    for (let k = 1; k < deg; k++) {
      g[u].push({ to: Math.floor(rnd() * V), weight: 1 + Math.floor(rnd() * maxWeight) });
    }
  }
  return g;
}
 
/** The main loop again, with the stale check switchable and edge scans counted. */
function countEdgeScans(graph: WeightedGraph, source: number, staleCheck: boolean): number {
  const dist = new Array<number>(graph.length).fill(Infinity);
  const pq = new MinHeap();
  let scans = 0;
  dist[source] = 0;
  pq.push(source, 0);
  for (;;) {
    const entry = pq.pop();
    if (entry === undefined) break;
    const { node: u, distance: d } = entry;
    if (staleCheck && d > dist[u]) continue;
    for (const edge of graph[u]) {
      scans++;
      const candidate = d + edge.weight;
      if (candidate < dist[edge.to]) { dist[edge.to] = candidate; pq.push(edge.to, candidate); }
    }
  }
  return scans;
}
 
for (const V of [20_000, 100_000, 400_000]) {
  const g = benchGraph(V, 8, 100, V);
  const kept = countEdgeScans(g, 0, true);
  const dropped = countEdgeScans(g, 0, false);
  console.log(`V=${V}  with check ${kept}  without ${dropped}  ratio ${(dropped / kept).toFixed(2)}x`);
}
// V=20000  with check 160000  without 284824  ratio 1.78x
// V=100000  with check 800000  without 1426688  ratio 1.78x
// V=400000  with check 3200000  without 5706584  ratio 1.78x

With the check, edge scans equal E exactly — every edge is examined once, which is what "each vertex is settled once" means in practice. That column is a property of the algorithm and it holds whatever graph you feed it. The without column is a property of these graphs. It counts re-relaxations, and re-relaxations need room for a cheaper route to arrive late, which is a question about the weights and nothing else.

That is measurable too, and it is the reason the ratio sat at 1.78 in all three rows above rather than drifting with size. Same generator, same degree, only maxWeight moved:

Read down a column and the ratio moves by a factor of 1.8. Read across a row and it barely moves at all, over a 20x change in graph size. The number belongs to the weight distribution, not to V — with every weight equal to 1 the check saves you literally nothing, because no route can ever arrive late and cheaper. Quote 1.78x without saying "uniform integers in 1..100" and you have quoted a constant that is not one.

In wall clock at V = 400,000 with weights in 1..100, 78% more edge scans cost about 30% more time: 649 ms with the check against 846 ms without, median of nine alternating runs in one process. It is a performance bug rather than a correctness bug, which is exactly why a test suite will not find it for you.

The naive FIFO version is not exponential. You will see the claim that queue-based relaxation degrades to factorial or exponential time. It does not. Over 400 random graphs the ratio of queue pops to V * E never exceeded 1.00, and the only graphs that reached it were two-node ones where the bound is trivially tight. On a hand-built adversarial chain designed to force repeated re-relaxation (25 nodes, 36 edges) it did 235 pops against a V * E bound of 900 — and against 25!, which is about 1.6e25. The Bellman-Ford-Moore bound of O(V * E) holds because a FIFO queue processes nodes in passes, and after pass i every shortest path using at most i edges is final.

Where it breaks: negative edges

Every article says Dijkstra "does not work with negative weights". Here is the actual output.

// 0 -> 3 costs 3 directly. 0 -> 1 -> 3 costs 4 + (-3) = 1.
const trap: WeightedGraph = [
  [{ to: 3, weight: 3 }, { to: 1, weight: 4 }],
  [{ to: 3, weight: -3 }],
  [],
  [],
];
 
console.log(shortestPath(trap, 0, 3));
// { distance: 3, path: [ 0, 3 ] }   <- wrong; the real answer is 1
console.log(floydWarshall(trap)[0][3]);
// 1

No exception, no warning, no infinite loop. A confident, wrong 3, with a plausible-looking path attached. Node 3 was settled at distance 3 while node 1 was still sitting in the heap at 4, and the early exit fired. The greedy rule assumes a settled node can only get more expensive from here; a negative edge is exactly the thing that makes that false.

Changing the relaxation step

Once the loop is in muscle memory, most of the harder graph problems are one edited line.

LeetCode 787, Cheapest Flights Within K Stops. Plain Dijkstra settles a node the first time it is cheapest and never revisits it, so it will lock in a 5-hop bargain and never find the 2-hop route you are allowed to take. Widen the state: settle (node, stopsUsed) instead of node, so dist becomes 2D. Same loop, bigger key.

LeetCode 1631, Path With Minimum Effort. The cost of a path is the largest single step on it, not the sum. Replace d + edge.weight with Math.max(d, edge.weight). That works for the same reason the original does: Math.max is monotonic and never decreases along a path, which is the only property the greedy rule needs. Sum is not special; non-negativity is.

A-star. Order the heap by dist[u] + h(u) instead of dist[u], where h estimates the remaining distance to the target — straight-line distance, for maps. The catch that gets left out: optimality holds only if h never overestimates the true remaining cost. Overestimate and A-star gets faster and starts returning wrong paths.

The answer that does not look wrong

Of everything in this post, the output I keep coming back to is { distance: 3, path: [ 0, 3 ] }. It has a distance. It has a path. The path is a real edge in the graph. The number is wrong by a factor of three and there is nothing on the screen to tell you so — no throw, no NaN, no warning, no hang. If that graph had been a pricing table or a routing table, the first person to find out would have been a customer.

Which is why the choice of algorithm is a decision you make before you write anything, not a thing you discover afterwards:

Someone will ask about O(E + V log V). That is the Fibonacci heap bound from Fredman and Tarjan's 1984 paper, which gets amortised constant-time decreaseKey. It is asymptotically better, and the constant factors are famously bad enough that the received wisdom is that it loses to a binary heap at any size you would actually run. I did not measure that one, so treat it as received wisdom rather than as a result — it is the only claim in this post that is not a number off this machine.

Whatever you implement, walk the reconstructed path afterwards: check that every edge on it exists, then that its weights sum to the distance you reported. Six lines. In my mutation runs the edge-existence check fired first and the weight check caught cases it missed, and between them they are the only thing that noticed a broken prev[] at all. The distance assertions were perfectly happy.