9 Floyd-Warshall Algorithm
This chapter covers
- Computing the shortest path between all pairs of nodes in a dense graph
- Constructing a dynamic programming matrix using intermediate vertices
- Evaluating algorithmic trade-offs, negative weight cycles, and time complexity
In previous chapters, we abandoned mathematical perfection to find a “good enough” answer using Ant Colony Optimization. We did that because the state space was too massive, and we traded absolute certainty for extreme computational speed. Knapsack taught us how to utilize the dynamic programming approach to solve the overlapping subproblems. But what if you are working with a constrained, highly dense graph where you absolutely must know the exact optimal route between every single pair of nodes in advance? In this chapter, we return to dynamic programming to solve the All-Pairs Shortest Path problem.
The Floyd-Warshall algorithm, published in 1962 by Robert Floyd and Stephen Warshall, solves a very specific architectural problem. You likely already know Dijkstra's algorithm, which finds the shortest path from one single starting point to every other node. But if you need to know the shortest path from every node to every other node, you would have to execute Dijkstra's algorithm from scratch for every single vertex. On a dense graph (see 9.3.3), that is computationally wasteful.