Shortest Paths with Dijkstra

BFS finds the route with the fewest edges. That is the right answer only when every edge costs the same. Put real numbers on them, distances, latencies, fares, and the fewest-hops route is frequently the expensive one. Two short hops beat one long haul all the time.

Dijkstra's algorithm handles this. It is the thing inside your maps app, and the idea behind it is smaller than its reputation suggests.

The one rule

Keep a best-known cost for every node. The source starts at 0 because standing still is free, and everything else starts at infinity because you have not found any route to it yet. Then repeat:

Pick the cheapest node you have not finalised yet. Lock its number in permanently. Then look at its neighbours and ask, for each one, whether going through this node beats the best route you knew about. If it does, write down the better number.

That last step has a name you will see everywhere: relaxing an edge. It sounds mysterious and means "check whether this edge gives a cheaper route, and update if so". That is all.

Watch the numbers fall

The number floating above each node is its current best-known cost. Play this through and watch them drop from infinity as better routes get discovered. The panel on the right shows which ones are locked in.

Look at what happens to B specifically. It starts at 4, because the direct edge A→B costs 4. Then C gets finalised at 2, and suddenly B improves to 3, because going A→C→B costs 2 plus 1. The direct edge was not the cheapest route to a direct neighbour. That is the whole reason this algorithm has to exist.

The second example, "The long way is cheaper", pushes that idea as far as it will go. There is a direct A→B edge costing 10, sitting right next to a three-hop detour A→C→D→B costing 1 plus 1 plus 1. Watch B start at 10 and fall to 3, and E start at 20 and fall to 5. A route with three times as many edges wins by a factor of three. If you had reached for BFS here, it would have confidently handed you the one-hop path and been wrong by 7.

Why locking a node in is safe

This is the part that deserves a minute. Why can Dijkstra permanently commit to a node's cost without ever revisiting it? What if a better route shows up later?

It cannot. Suppose we are about to lock in node X at cost 7, meaning X is the cheapest unfinalised node. Any alternative route to X has to leave the finalised set at some point, through some unfinalised node Y. But we picked X because it was the cheapest unfinalised node, so Y already costs at least 7. Then you would still have to travel from Y onwards to X, adding more. So the alternative is at least as expensive. There is no room for a surprise.

Notice the hidden assumption: adding more edges only ever makes a route more expensive. That holds because weights are not negative. Break that assumption and the proof falls apart, which is exactly what happens next.

Dijkstra breaks on negative weights

If an edge can have a negative weight, going further can make a route cheaper. Now locking a node in is no longer safe, because a bargain edge further out could undercut a decision you already made and refuse to revisit.

A --(2)--> B
A --(5)--> C
B --(-4)-> C

Dijkstra locks C at 5, because 5 beats the other options it can see.
The real answer is 2 + (-4) = -2, via B.
By the time B is processed, C is already finalised and never reconsidered.

This is not a bug you can patch. It is the price of the greedy shortcut that makes Dijkstra fast. For negative weights you need Bellman-Ford, which is slower and gets its own lesson in the advanced section.

In code

function dijkstra(adj, nodes, start) {
  const dist = new Map(nodes.map((n) => [n, Infinity]));
  const parent = new Map();
  const done = new Set();
  dist.set(start, 0);

  while (done.size < nodes.length) {
    // Cheapest unfinalised node. A real implementation uses a
    // priority queue here; this scan is O(V) and easier to read.
    let current = null;
    let best = Infinity;
    for (const [node, d] of dist) {
      if (!done.has(node) && d < best) {
        best = d;
        current = node;
      }
    }

    if (current === null) break; // rest of the graph is unreachable
    done.add(current);

    for (const { to, weight } of adj.get(current) ?? []) {
      if (done.has(to)) continue;
      const candidate = best + weight;
      if (candidate < dist.get(to)) {
        dist.set(to, candidate);   // relax the edge
        parent.set(to, current);
      }
    }
  }

  return { dist, parent };
}

That inner scan for the cheapest node is the slow part, giving O(V²) overall. Swap it for a binary heap and you get O((V + E) log V), which is what any serious implementation does. The logic does not change, only how fast you can find the minimum.

Also worth noticing: if every weight is 1, Dijkstra degenerates into BFS. The cheapest unfinalised node is always the one at the current ring. Same algorithm underneath, which is a satisfying thing to realise.

Check yourself