4.19.3 — Shortest Paths: Dijkstra, Bellman-Ford, Floyd-Warshall & A*

BFS finds the path with the fewest edges. On a road map that is the route with the fewest junctions, which may well be twice as long in kilometres as a route with more junctions.

The moment edges carry different weights — distance, time, money, latency — "fewest hops" and "cheapest" stop being the same question, and you need a different algorithm. Which one depends on exactly three things: whether weights can be negative, whether you need one source or all pairs, and whether you have any extra knowledge about where the target is.

1. Dijkstra: always expand the cheapest known frontier

Dijkstra's algorithm (Edsger Dijkstra, 1956, reportedly designed in about twenty minutes in a café) works on graphs with non-negative edge weights and finds the cheapest path from one source to every vertex.

The idea is one sentence: among all vertices whose cost you know but whose neighbours you have not yet explored, always expand the cheapest one. That is BFS with a priority queue in place of the queue, and the priority queue is the heap from Chapter 4.16.

function dijkstra(source: number, adj: Map<number, [number, number][]>, n: number): number[] {
  const dist = new Array(n).fill(Infinity);        // (1)
  dist[source] = 0;
  const heap = new MinHeap<[number, number]>((a, b) => a[0] - b[0]);   // (2)
  heap.push([0, source]);

  while (heap.size() > 0) {
    const [d, node] = heap.pop()!;
    if (d > dist[node]) continue;                  // (3)  a stale entry — skip it
    for (const [next, weight] of adj.get(node) ?? []) {
      const candidate = d + weight;                // (4)
      if (candidate < dist[next]) {                // (5)
        dist[next] = candidate;
        heap.push([candidate, next]);              // (6)
      }
    }
  }
  return dist;
}

1. Infinity means "no route found yet". Every comparison against it works naturally, with no special case.
2. The heap orders by cost, so pop always yields the cheapest unexplored frontier vertex. Entries are [cost, vertex] pairs.
3. This line is the lazy-deletion trick from Chapter 4.6. When a shorter route to a vertex is found, we push a new entry rather than trying to move the old one, so the heap accumulates stale entries. If the popped cost is worse than the best we now know, that entry is obsolete and we skip it. The alternative is an indexed heap with a decrease-key operation, which is more code for a small constant-factor gain.
4. Relaxation: the cost of reaching next through node.
5. Only if it beats the best route we already had.
6. Push the improvement. A vertex can be pushed several times, which is what makes step 3 necessary.

Complexity is O((V + E) \log V) with a binary heap. Each edge can cause at most one push, so the heap holds at most E entries and each operation is \log E, which is O(\log V) since E \le V^2.

Why it needs non-negative weights, precisely. Dijkstra's correctness rests on one claim: when a vertex is popped from the heap, its recorded distance is final. The argument is that any other route to it must go through some vertex still in the heap, which costs at least as much as this one, and then add more edges on top — so it cannot be cheaper.

That last step assumes adding an edge never reduces the total. With a negative edge it can. Consider A →(1)→ B and A →(5)→ C →(−10)→ B. Dijkstra pops B at cost 1, marks it final, and never revisits it — missing the real answer of −5. It does not merely get a worse answer; it confidently reports a wrong one, which is exactly why the precondition matters and why "just add a constant to every weight to make them positive" does not work. Adding a constant penalises paths with more edges, so it changes which path is cheapest.

Where you actually meet it: routing protocols (OSPF, which drives IP routing inside a network — Chapter 5.3), map navigation, network latency-aware load balancing, and any "cheapest sequence of steps" problem. Also, unexpectedly, problems that are not about distance at all: "the path that minimises the maximum edge" and "the path with the highest probability" are both Dijkstra with the relaxation rule changed.

2. Bellman-Ford: slower, but it survives negative weights

Bellman-Ford handles negative edges by giving up the clever ordering and simply relaxing every edge, V−1 times.

function bellmanFord(source: number, edges: [number, number, number][], n: number): number[] | null {
  const dist = new Array(n).fill(Infinity);
  dist[source] = 0;

  for (let round = 0; round < n - 1; round++) {          // (1)
    let changed = false;
    for (const [a, b, w] of edges) {
      if (dist[a] !== Infinity && dist[a] + w < dist[b]) {   // (2)
        dist[b] = dist[a] + w;
        changed = true;
      }
    }
    if (!changed) break;                                 // (3)
  }

  for (const [a, b, w] of edges) {                       // (4)
    if (dist[a] !== Infinity && dist[a] + w < dist[b]) return null;
  }
  return dist;
}

1. Why exactly V−1 rounds? Any shortest path visits each vertex at most once, so it has at most V−1 edges. After round k, every shortest path using at most k edges is correct — each round extends the guaranteed-correct paths by one more edge. After V−1 rounds every shortest path is covered.
2. The same relaxation as Dijkstra, applied blindly to every edge.
3. If a full round changes nothing, nothing will ever change again, so stop early. On most real graphs this ends long before V−1 rounds.
4. The negative-cycle check, and it is the algorithm's real superpower. After V−1 rounds everything should be final. If one more relaxation still improves something, then there is a cycle whose total weight is negative — go round it again and the cost drops again, forever. There is no shortest path, and reporting that is the correct answer.

O(VE) time, which on a dense graph is O(V^3) — far worse than Dijkstra. You pay that for two capabilities: negative weights, and negative-cycle detection.

Where negative weights are real. Currency arbitrage is the classic: take the negative logarithm of each exchange rate, and a negative cycle is a sequence of trades that returns more money than you started with. Also cost models where some steps pay you (a rebate, a refunded deposit, energy recovered by braking) and constraint systems where "x must be at least 5 more than y" becomes a negative edge.

Where you actually meet it: the distance-vector routing protocols that predate OSPF (RIP is essentially distributed Bellman-Ford), and Chapter 5.3's routing discussion.

3. Floyd-Warshall: every pair, in three loops

When you need the distance between every pair of vertices and the graph is small and dense, running Dijkstra V times is one option. Floyd-Warshall is simpler, handles negative edges, and is three nested loops.

function floydWarshall(dist: number[][]): void {          // (1)  dist starts as the weight matrix
  const n = dist.length;
  for (let k = 0; k < n; k++)                             // (2)  ← the intermediate vertex, OUTERMOST
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);   // (3)
}

1. Input and output are the same matrix: dist[i][j] starts as the direct edge weight (or Infinity), and ends as the shortest path.
2. The loop order is the algorithm, and swapping the loops breaks it. After iteration k, dist[i][j] holds the shortest path from i to j using only vertices 0..k as intermediate stops. The k loop must be outermost so that this claim is true for all pairs before k advances.
3. Either the best route so far, or a route that detours through k. One line.

O(V^3) time, O(V^2) space. Practical up to a few hundred vertices — 500 vertices is 1.25 \times 10^8 operations, which is under a second, and 5,000 vertices is 1.25 \times 10^{11}, which is not.

Negative edges are fine. A negative cycle shows up as a negative value on the diagonal: dist[i][i] < 0 means you can get back to i having gained value, which is impossible without a negative cycle.

4. A*: Dijkstra with a hint about where the goal is

Dijkstra expands in every direction equally, like a circular ripple. If you are routing from London to Edinburgh, it happily explores Cornwall on the way, because it has no idea where Edinburgh is.

A* adds one thing: a heuristic h(v), an estimate of the remaining distance from v to the goal. Instead of ordering the heap by cost-so-far g(v), it orders by

f(v) = g(v) + h(v)

which is "cost so far plus estimated cost remaining". Vertices that lead toward the goal get explored first, and the search becomes a beam pointing at the target rather than a circle.

The heuristic must be admissible: it must never overestimate the true remaining distance. Straight-line distance is the standard choice for maps, because the real road distance can only be longer than the direct line.

Why admissibility is required. If h overestimates the remaining distance from some vertex, A* may push that vertex far back in the queue and finish via a worse route before ever examining it — returning a path that is not optimal. Under-estimating is always safe; the worst it costs you is extra exploration. With h = 0 everywhere, A* is Dijkstra, which is the cleanest way to see the relationship.

Where you actually meet it: game pathfinding on a grid (where the heuristic is Manhattan or diagonal distance), robot navigation, and real map routing — though production map engines use much heavier machinery on top, particularly contraction hierarchies, which precompute shortcuts so a continent-scale query takes microseconds.

5. Choosing, in one table

Situation	Algorithm	Cost
Unweighted, one source	BFS	O(V+E)
All weights equal	BFS	O(V+E)
Non-negative weights, one source	Dijkstra	O((V+E)\log V)
Negative weights possible	Bellman-Ford	O(VE)
Need to detect a negative cycle	Bellman-Ford	O(VE)
All pairs, small dense graph	Floyd-Warshall	O(V^3)
One target, good distance estimate	A*	≤ Dijkstra
Weighted DAG	topological order + relax	O(V+E)

The last row deserves its sentence, because it is the fastest of all and people miss it. On a DAG there are no cycles, so a topological order (Chapter 4.19.2) guarantees that when you reach a vertex, every route into it has already been finalised. Relax the edges in that order and you are done in linear time, with negative weights allowed. This is also exactly what dynamic programming does — Chapter 4.22 makes the connection explicit, because every DP problem is a shortest-path problem on a DAG of states.

The 0-1 BFS special case. If every edge weighs either 0 or 1, you do not need a heap. Use a deque (Chapter 4.7): push 0-weight moves to the front and 1-weight moves to the back. The deque stays sorted by cost automatically, and the whole thing runs in O(V+E). This solves the family of grid problems where some moves are free and some cost one, such as "minimum walls to break through to reach the exit".

6. Reconstructing the path, not just the distance

Every algorithm above returns distances. Getting the actual route needs one extra array.

const prev = new Array(n).fill(-1);        // (1)
// inside the relaxation:
if (candidate < dist[next]) {
  dist[next] = candidate;
  prev[next] = node;                       // (2)  remember who got us here cheapest
  heap.push([candidate, next]);
}

function pathTo(target: number, prev: number[]): number[] {
  const path: number[] = [];
  for (let at = target; at !== -1; at = prev[at]) path.push(at);   // (3)
  return path.reverse();                                          // (4)
}

1. prev[v] is the vertex we arrived from on the best known route to v.
2. Updated exactly when the distance improves, so it always reflects the current best route.
3. Walk backwards from the target following the parent links.
4. Reverse, because we collected it from the end.

The same prev array works for BFS, Dijkstra and Bellman-Ford unchanged. This is worth doing unprompted in an interview — the question is usually stated as "find the shortest path", and returning only its length is answering a different question.

What the interviewer will push on

"Why does Dijkstra fail on negative edges? Can I just add a constant to make them positive?" Two-part answer. Dijkstra assumes a popped vertex is final, which holds only if extending a path never reduces its cost. And no, adding a constant does not fix it, because it penalises paths in proportion to their edge count, changing which path is cheapest. That second half is the part most candidates miss.

"What is the complexity of Dijkstra?" O((V+E)\log V) with a binary heap. If they push further: a Fibonacci heap gives O(E + V\log V) in theory and loses in practice on constant factors (Chapter 4.16).

"How does Dijkstra update a vertex already in the heap?" Either lazy deletion — push a duplicate and skip stale pops by comparing against the recorded distance — or an indexed heap with a decrease-key. Naming both, and saying lazy deletion is what you would actually write, is the strong answer.

"Why exactly V−1 rounds in Bellman-Ford?" A shortest path visits each vertex at most once, so it has at most V−1 edges, and each round extends the guaranteed-correct prefix by one edge. Then volunteer the V-th round: if anything still improves, there is a negative cycle.

"Can I use Dijkstra on a graph with weight 0 edges?" Yes — zero is non-negative and the correctness argument holds. Then mention 0-1 BFS as the faster specialisation when every weight is 0 or 1.

"You have a DAG with negative weights. What now?" Topological order plus a single relaxation pass, O(V+E), faster than everything else on the list. This is the answer that shows you are reasoning about preconditions rather than reaching for the biggest hammer.

One thing to volunteer: point out that the shortest-path tree is not the minimum spanning tree, with the triangle example from 4.19.2. Interviewers hear these conflated constantly, and separating them cleanly signals you know what each algorithm is optimising.

Recall

• Dijkstra is BFS with a heap: always expand the cheapest frontier vertex. O((V+E)\log V), and it requires non-negative weights because it assumes a popped vertex is final.
• Adding a constant to make weights positive does not work — it penalises paths by their edge count and changes which path is cheapest.
• Bellman-Ford relaxes every edge V−1 times (O(VE)) because a shortest path has at most V−1 edges; a V-th round that still improves anything proves a negative cycle.
• Floyd-Warshall is three loops with the intermediate vertex k outermost; O(V^3), all pairs, negative edges fine, and dist[i][i] < 0 flags a negative cycle.
• A* orders by f = g + h and needs an admissible heuristic that never overestimates; with h = 0 it is exactly Dijkstra.
• On a DAG, topological order plus one relaxation pass is O(V+E) and allows negative weights — the fastest option, and the same shape as dynamic programming.
• Keep a prev[] array during relaxation to reconstruct the actual path, not just its length.

Self-test: Give a small graph where Dijkstra returns a wrong answer, and say which vertex it finalises too early · Why does adding a constant to all weights not repair it? · Why is the k loop outermost in Floyd-Warshall? · What happens to A* if the heuristic overestimates? · Which algorithm handles a weighted DAG fastest, and why does it beat Dijkstra?

Next: 4.20 is the graph problem set — thirteen problems, and nearly all of them are one of three things: flood fill on a grid, breadth-first search for a shortest path, or a topological sort over dependencies.