Advanced · Module 17
Shortest paths
Dijkstra, Bellman-Ford, A* and all-pairs shortest paths, and when each applies.
Finding the cheapest route through a weighted network is one of the oldest problems in computing, and the right algorithm depends on the weights and on what you need. This module covers Dijkstra's algorithm for non-negative weights, Bellman-Ford for negative weights and negative cycles, A* for guiding a search toward a single goal, and Floyd-Warshall for every pair at once, with the proofs that explain when each one is correct.
- 1Dijkstra's algorithmPro — members onlyWith non-negative edge weights, the unsettled vertex with the smallest tentative distance can never be improved, so Dijkstra's algorithm settles vertices one at a time in distance order, using a min-heap.15 min
- 2Negative edges and Bellman-FordPro — members onlyWhen some weights are negative, Dijkstra's settled distances can be wrong. Bellman-Ford relaxes every edge V − 1 times instead, handles negative weights, and detects negative cycles, at a cost of O(V × E).14 min
- 3A* and heuristicsPro — members onlyA* is Dijkstra's algorithm with a sense of direction: it orders vertices by distance so far plus an estimate of the distance remaining. If the estimate never overestimates, the path it finds is still optimal, usually after exploring far less.14 min
- 4Floyd-WarshallPro — members onlyFloyd-Warshall computes the shortest path between every pair of vertices with three nested loops over a distance matrix. Its outer loop allows one more intermediate vertex at a time, which is a dynamic program in disguise.14 min