Floyd-Warshall: Allowing One More Stop Each Round

Floyd-Warshall finds the shortest distance between every pair of vertices at once, in a table with a row and a column per vertex. It fills the table in rounds, one per vertex, and each round allows that vertex as a stop. This card says exactly what the table holds after each round, runs it on the topic's graph, and rebuilds a path from a second table.

The table starts with 0 from each vertex to itself, each edge's weight, and ∞ everywhere else: routes with no stops. The round for vertex k then asks, for every pair i and j, whether going from i to k and then from k to j beats the entry for i to j, and keeps the shorter. After the round for k, entry (i, j) holds the shortest distance from i to j using only stops among the vertices up to k, the vertices whose rounds have run. After the last round every vertex is allowed, so every entry is final.

The steps below are from a run, with the vertices taken in the order A to E. Entries the round changed are in [ ].

The last table's row for A matches the distances Dijkstra's algorithm settled from A, 0, 2, 5, 7 and 8, and the other rows are the answers from every other source, computed in the same run. The ∞ entries below the diagonal are real: no edge leads back towards A, so no route exists.

Round k is not "paths of at most k edges". That is what Bellman-Ford's pass k guarantees. After round C, A to D is 7 along A->B->C->D, three edges, because B and C are both allowed as stops. The rounds count which vertices may be passed through, not how many edges are used.

To rebuild a path, keep a second table, next hop: for each pair, the first vertex to go to from i on the best route to j. It starts as j for every edge i->j, and whenever a round improves (i, j) through k, next hop (i, j) becomes next hop (i, k). From A towards E the run's next hops were B, then C, then D, then E, so the path is A B C D E.

The loop over k must be the outermost of the three. With k inside, an entry would be decided before the entries it depends on were final. Negative weights are allowed; a negative cycle shows up as a negative entry on the diagonal, a vertex whose route back to itself costs less than nothing.

Reach for Floyd-Warshall when every pair is needed and the graph has a few hundred vertices at most: a table of travel times between every pair of towns, or how close every pair of routers is.