Chapter 6
Shortest Paths
Four algorithms, one shared idea: keep a frontier of tentative distances and relax edges until the frontier is honest. What differs is what you are allowed to assume about the weights.
4 pages3,300 words13 problems1 interactive
1Dijkstra's AlgorithmThe greedy that works because distances only ever grow — with the proof, the four implementations, and the shapes of problem that are one Dijkstra away.2Bellman–Ford and Negative Weightsn−1 rounds of relaxation, why that is enough, and the two extra lines that output the negative cycle.3Floyd–WarshallThree nested loops, every pair of vertices, and a dozen problems that are "Floyd, but the operation is not min".40-1 BFS, Dial, Potentials, JohnsonWhat to run when the weights are small, zero-one, or negative — with the invariant that makes each one correct.