Module 26
Shortest Paths
Cheapest routes in weighted graphs: Dijkstra with a heap, Bellman-Ford for negative weights and edge limits, Floyd-Warshall for all pairs, and Dijkstra variants.
When edges have different costs (distances, times, prices), the path with the fewest edges isn't necessarily the cheapest, so plain BFS is no longer enough. Shortest-path algorithms find the cheapest route, and each one fits a different situation.
This module teaches Dijkstra's algorithm with a priority queue (the everyday choice for non-negative weights), Bellman-Ford (negative weights, "at most k edges"), and Floyd-Warshall (all pairs on small graphs). It then shows how changing what "cost" means turns Dijkstra into a tool for bottleneck paths, probabilities and counting shortest routes.
Best after: Breadth-First Search, Heaps and Priority Queues
Part 1
Learn the ideas
- 26.1Dijkstra's AlgorithmAlways expand the unfinished node with the smallest known distance. With non-negative weights that distance is final, so each node is settled once.16 min
- 26.2Bellman-Ford and Floyd-WarshallBellman-Ford relaxes every edge V − 1 times and handles negative weights; round i allows paths of up to i edges. Floyd-Warshall finds all-pairs distances in O(V³).14 min
- 26.3Changing What "Cost" MeansDijkstra works for any path cost that never gets better as the path grows: sums, maximums (bottlenecks), products of probabilities ≤ 1, and extra state such as stops used.10 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
Plain Dijkstra: the answer is the largest shortest distance.
Minimax Dijkstra on a grid: a path's cost is its largest step.
Bellman-Ford limited to k + 1 edges, relaxing from a copy each round.
Dijkstra with a max-heap and multiplication.
All-pairs distances with Floyd-Warshall on a small graph.
Bottleneck path on a grid: the time needed is the highest cell on the best route.
Counting shortest paths during Dijkstra.