Graphs and Shortest Paths

Six towns joined by roads, each road with a length. What is the shortest drive from A to F?

The honest answer is a question back: what do the road lengths look like? That sounds pedantic, but the wrong choice here does not crash — it returns a route that is confidently, silently wrong.

First: a graph is just two lists

Before any algorithm, get the data structure straight, because most confusion about graphs is confusion about how they are stored.

// "Which places can I reach directly from here, and at what cost?"
const graph = new Map<string, [string, number][]>([
  ['A', [['B', 4], ['C', 2]]],
  ['B', [['A', 4], ['C', 1], ['D', 5]]],
  // …
]);

This is an adjacency list: for each node, the neighbours. Undirected roads appear twice — once from each end — because “reachable from” has to be answerable from both sides.

The obvious way, and why it fails

Try every route and keep the shortest. On a graph with cycles, “every route” is infinite — you can lap a loop forever — so you would need to forbid revisits, and that turns into exploring every simple path, of which there can be factorially many.

Twelve towns is already more routes than a laptop will enumerate in a day.

Case 1: every edge costs the same

If all roads are the same length, “shortest” just means “fewest roads”, and breadth-first search answers it:

function bfs(graph: Graph, start: string) {
  const dist = new Map([[start, 0]]);
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift()!;
    for (const [next] of graph.get(node) ?? []) {
      if (dist.has(next)) continue;               // already found, and found sooner
      dist.set(next, dist.get(node)! + 1);
      queue.push(next);
    }
  }
  return dist;
}

BFS visits everything one step away, then everything two steps away, and so on. The first time it reaches a node it has reached it in the fewest steps, which is why if (dist.has(next)) continue is safe.

$O(V + E)$, and it needs no priority queue. If your edges are unweighted, stop here — reaching for anything cleverer is a mistake.

Case 2: weights differ, but none is negative

Now “fewest roads” and “shortest drive” come apart: three short hops can beat one long one. BFS gets this wrong because it counts hops.

Dijkstra’s algorithm fixes it with one change: instead of the node that is fewest hops away, always work on the node with the smallest distance so far.

Watch which node it picks each round:

Two things are happening each step, and they are worth naming separately:

1. Settle — take the unfinished node with the smallest estimate. Its estimate is now final.
2. Relax — for each of its neighbours, check whether going via this node beats the neighbour’s current estimate. If so, lower it.

Why settling is allowed

This is the whole proof, and it is short.

Say u has the smallest estimate of everything unfinished. Could there be a cheaper route to u that we have not seen? Such a route would have to leave the settled region through some other unfinished node v first — but dist[v] is at least dist[u] by choice of u, and going onward from v only adds more.

So no. The estimate is already the answer.

The code

function dijkstra(graph: Graph, start: string): Map<string, number> {
  const dist = new Map([[start, 0]]);
  const done = new Set<string>();
  const queue = new MinHeap<[number, string]>();   // ordered by distance
  queue.push([0, start]);

  while (queue.size > 0) {
    const [d, node] = queue.pop()!;

    // Stale entry: we already settled this node via a cheaper route.
    if (done.has(node)) continue;
    done.add(node);

    for (const [next, weight] of graph.get(node) ?? []) {
      const candidate = d + weight;
      if (candidate < (dist.get(next) ?? Infinity)) {
        dist.set(next, candidate);
        queue.push([candidate, next]);             // the old entry stays, and is skipped above
      }
    }
  }
  return dist;
}

The done check exists because most heaps cannot lower an existing key. Rather than fight that, push a second entry and ignore the outdated one when it surfaces. It costs a little memory and is far simpler than the alternative.

With a binary heap this is $O((V + E)\log V)$.

Case 3: negative weights

Then use Bellman-Ford. It gives up on being clever: relax every edge, $V-1$ times over.

for (let i = 0; i < nodeCount - 1; i += 1) {
  for (const [u, v, w] of edges) {
    if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
  }
}

$V-1$ rounds because any shortest path has at most $V-1$ edges, and each round guarantees one more edge of every path is correct.

There is a bonus. Run one extra round: if anything still improves, the graph has a negative cycle — a loop you can go round to keep getting cheaper — and “shortest path” is meaningless. Detecting that is often the real reason to choose Bellman-Ford, and it is the standard way to spot an arbitrage loop when edges are exchange rates.

$O(V \cdot E)$: much slower, and it is buying you something specific.

Case 4: you need every pair

Floyd-Warshall, three nested loops, and the ordering of them is the trick:

for (const k of nodes)          // ← the intermediate node. Must be outermost.
  for (const i of nodes)
    for (const j of nodes)
      dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

Read k as “am I allowed to route through k?”. After the k-th pass, every dist[i][j] is the best route using only the first k nodes as stops. Widening that permission one node at a time is what makes it correct.

$O(V^3)$, which is fine up to a few hundred nodes and never beyond.

Choosing

A* is worth a footnote: it is Dijkstra with the queue ordered by distance so far + estimated distance remaining. Feed it straight-line distance on a map and it heads towards the goal instead of expanding in all directions. The estimate must never overshoot the true remaining distance — an optimistic guess keeps the settling argument intact, an over-confident one breaks it in exactly the way negative weights do.