Floyd-Warshall algorithm
Find shortest paths between every pair of vertices by asking whether each vertex is useful as an intermediate stop.
Big idea
How it thinks about the graph
Instead of solving from one start vertex, update a whole distance table by allowing more and more possible intermediate vertices.
Useful when
Small dense graphs, all-pairs shortest paths and matrix-style dynamic programming.
Watch out: It considers every triple of vertices, so it becomes expensive on large graphs.
Questions to investigate
What does each entry in the distance table represent?
How can allowing one new intermediate vertex improve many paths?
When is an all-pairs answer more useful than a single route?
Interactive version planned
The page is here now so the topic has a clear place in the site. The next step will be to build a visual step-through version of the algorithm.