Module A-6·11 min read

Single-source shortest path with a min-heap — the algorithm behind every non-negative-weight routing problem.

Written by Jatin Jain Saraf · Architect of SupraScan

Module A-6 — Shortest Paths I: Dijkstra's Algorithm

What this module covers: Module A-5's BFS finds shortest paths measured in hop count — correct only when every edge costs the same. This module covers the weighted version: Dijkstra's algorithm, which is BFS with one structural swap — Module A-1's min-heap standing in for Module F-7's plain queue — always processing whichever unvisited node currently has the smallest known total distance, not just whichever was enqueued first.

Why BFS Breaks on Weighted Graphs

BFS's shortest-path guarantee (Module A-5) depends entirely on every edge costing exactly the same "1 hop." On a weighted graph, a path with fewer edges can easily cost more than a path with more edges that are individually cheaper — Module P-6 already flagged this exact failure mode. Dijkstra's algorithm fixes it by tracking actual accumulated cost, not hop count, and by always expanding outward from whichever reachable node currently has the smallest known cost — not whichever was simply discovered first.

The Algorithm: BFS With a Min-Heap Instead of a Queue

function dijkstra(
  graph: Map<string, [string, number][]>, // node -> [neighbor, edge weight][]
  start: string
): Map<string, number> {
  const distances = new Map<string, number>();
  const visited = new Set<string>();
  const minHeap = new MinHeap<[number, string]>(/* compare by first element — distance */);
 
  distances.set(start, 0);
  minHeap.insert([0, start]);
 
  while (!minHeap.isEmpty()) {
    const [dist, node] = minHeap.extractMin()!; // Module A-1 — always the smallest known distance so far
 
    if (visited.has(node)) continue; // a shorter path to this node was already finalized
    visited.add(node);
 
    for (const [neighbor, weight] of graph.get(node) ?? []) {
      const newDist = dist + weight;
      if (newDist < (distances.get(neighbor) ?? Infinity)) {
        distances.set(neighbor, newDist);
        minHeap.insert([newDist, neighbor]); // a cheaper route to `neighbor` was just found
      }
    }
  }
 
  return distances;
}

Compare this line-by-line against Module A-5's shortestPathLength: same overall shape (extract a node, look at its neighbors, push newly-discovered or improved distances), but Module F-7's plain FIFO queue is replaced by Module A-1's min-heap, and instead of tracking "distance = hop count," distances tracks actual accumulated edge weight. Always extracting the minimum is what makes this correct: once a node is popped from the min-heap, no undiscovered path could possibly reach it more cheaply, because every alternative path would have to go through some other node whose distance is at least as large as what's currently at the top of the heap — there's nothing left in the heap with a smaller distance that could somehow produce a shorter route.

Why This Only Works With Non-Negative Weights

The correctness argument above — "no path through a not-yet-processed node could possibly be cheaper" — depends entirely on edge weights never being negative. If a negative edge existed, a longer-looking path that later dips through a large negative weight could end up cheaper than a path Dijkstra already finalized and moved past, and Dijkstra has no mechanism to revisit a node it's already marked visited and committed to.

// Why negative weights break Dijkstra's greedy assumption:
// A -> B: weight 5
// A -> C: weight 2
// C -> B: weight -10
//
// Dijkstra finalizes distance to B as 5 (via A directly) before ever considering C's
// path, because 2 < 5 means C gets processed... but if C -> B costs -10, the true
// shortest path to B is 2 + (-10) = -8, much cheaper than the 5 Dijkstra already locked in.