Dijkstra's Algorithm

Hook problem

BFS works when every edge costs one step. But roads, links, or choices often have different costs. Now the question is not “how many edges?” but “what is the smallest total cost from A?”

First naive idea

Try BFS anyway. It would discover B directly from A and keep the one-edge path A -> B, even though A -> C -> B costs less.

Where it breaks

In an unweighted graph, first discovery is enough. In a weighted graph, first discovery by edge count can freeze the wrong parent or cost.

The core invention

Dijkstra keeps a frontier like BFS, but the frontier is ordered by tentative total cost. A FIFO queue pops the oldest entry; a priority queue pops the smallest label.

Relaxation scaffold

Relaxation asks whether going through the current node improves a neighbor. For C -> B, the old dist[B] is 4, while dist[C] + 2 = 3, so B improves and its parent changes to C.

Interactive visual demo

Formal version

For every edge (u, v), Dijkstra requires w(u, v) >= 0. It keeps a tentative distance dist[v], a parent[v], a settled set of finalized nodes, and a priority queue of candidate entries.

The algorithm computes distances to all reachable nodes. We inspect F later as one recovered path, not because Dijkstra is only a single-target algorithm.

Implementation sketch

function dijkstra(start: NodeId, graph: WeightedGraph) {
  const dist = new Map<NodeId, number>([[start, 0]]);
  const parent = new Map<NodeId, NodeId>();
  const settled = new Set<NodeId>();
  const heap = new MinHeap([{ node: start, distance: 0 }]);

  while (!heap.isEmpty()) {
    const entry = heap.popMin();
    if (entry.distance !== dist.get(entry.node) || settled.has(entry.node)) continue;

    settled.add(entry.node);
    for (const edge of graph[entry.node]) {
      const candidate = entry.distance + edge.weight;
      if (settled.has(edge.to)) continue;
      if (candidate < (dist.get(edge.to) ?? Infinity)) {
        dist.set(edge.to, candidate);
        parent.set(edge.to, entry.node);
        heap.push({ node: edge.to, distance: candidate });
      }
    }
  }

  return { dist, parent };
}

Duplicate heap entries are allowed. The stale-entry guard skips an old entry when its distance no longer matches the best known dist[node].

Correctness intuition

Just before settling B, the heap minimum is (B, 3) and every other tentative entry is at least 4. Any hidden alternative path to B through unsettled nodes must first reach the frontier at cost >= 4, then add a nonnegative edge. It cannot beat 3.

Complexity

With a binary heap and duplicate entries, each successful relaxation pushes a heap entry. Each heap operation costs O(log V), so the usual bound is O((V + E) log V).

Common confusions

A priority queue is shown sorted here for reading, but a real heap only promises the next minimum. Old entries can remain in the heap and become stale.

Zero-weight edges are allowed. Equal tentative-distance ties can use a deterministic display order, but tie order is not what makes Dijkstra correct.

An unreachable node would keep distance Infinity and no parent.

Negative edges break the settled-state promise. This warning uses a separate directed graph, not the main undirected map.

Path recovery

Distances tell the cost. Parent pointers recover a concrete path by following arrows backward from the target and reversing the result.

Connections in the graph

Dijkstra generalizes BFS’s frontier-and-distance idea. BFS uses FIFO order because every edge costs one; Dijkstra uses tentative total cost because edges can have different nonnegative weights.

Exercises

1. After A settles, which heap entry should pop next?
2. Why does C -> B update B, but the later stale (B, 4) is skipped?
3. Reconstruct the path to F from the parent table.
4. In the directed negative-edge warning, what settled-state promise fails?

Graph connections : Dijkstra's Algorithm