SUNY Geneseo Department of Computer Science

The Floyd-Warshall Algorithm

Tuesday, March 26

CSci 242, Spring 2013
Prof. Doug Baldwin

Questions?

Problem?

Produce table of distances, D[i][j] = shortest distance from vertex i to vertex j

Carry it out

As dynamic programming
- Based on progressively expanding the set of vertices considered as intermediates on shortest paths
- Recurrence basically says the shortest path involving intermediate vertices numbered through k+1 is either the shortest path involving vertices through k (i.e., vertex k+1 doesn’t shorten the best path seen so far), or it’s a shortest path from the source vertex to vertex k+1, and then from k+1 to the destination—and neither of those segments uses vertex k+1, since doing so would create a cycle.
D⁰ = W (W is just initial adjacency matrix with edge weights)

Note as a shortcut that whenever d_ik = ∞, the ith row of D^k is the same as the ith row of D^k-1

Very important invariant: the kth row and column of D^k are unchanged from D^k-1

Problem set asks you to explain why this must be
This invariant means that actual implementations of this algorithm can use a single 2D array, not a 3D one, and update it in place without worrying about over-writing a value that will be needed in the future

Another approach to shortest paths

Chapter 24 introduction + Section 24.3