Every pair at once
Sometimes you need the shortest distance between every pair of vertices, not just from one source. Floyd Warshall computes all of these with a compact dynamic programming idea.
Allowing one more middle vertex
Keep a distance grid initialised with direct edge weights, infinity where no edge exists, and zero on the diagonal. Then consider each vertex k in turn as a permitted intermediate stop:
- For every pair of vertices i and j, ask whether going from i to k and then k to j is shorter than the current best from i to j.
- If so, update the i to j distance through k.
After every vertex has had its turn as an intermediate, every entry holds the true shortest distance, because any path's set of intermediate vertices was eventually all allowed.
Strengths and limits
- It is wonderfully simple, just three nested loops over the vertices.
- It tolerates negative edges, and a negative value appearing on the diagonal flags a negative cycle.
- Its cost grows with the cube of the vertex count, so it suits dense graphs of modest size, not huge sparse ones.
Key idea
Floyd Warshall lets each vertex serve as an intermediate in turn, relaxing every pair through it, so all pairs shortest paths emerge from three nested loops.