Improvement of Floyd-Warshall Algorithm

Explore the different techniques used to implement Floyd-Warshall algorithm variants efficiently.

Efficient shortest paths with restricted intermediate vertices

Our fast dynamic programming algorithm is still a factor of O(logV)O(\log V) slower in the worst case than the standard implementation of Johnson’s algorithm. A different formulation of shortest paths that removes this logarithmic factor was proposed twice in 1962, first by Robert Floyd and later independently by Peter Ingerman, both slightly generalizing an algorithm of Stephen Warshall published earlier in the same year. In fact, Warshall’s algorithm was previously discovered by Bernard Roy in 1959, and the underlying recursion pattern was used by Stephen Kleene in 1951.

Warshall’s (and Roy’s and Kleene’s) insight was to use a different third parameter in the dynamic programming recurrence. Instead of considering paths with a limited number of edges, they considered paths that can pass through only certain vertices. Here, “pass-through” means “both enter and leave;” for example, the path wxyzw\rightarrow x\rightarrow y\rightarrow z starts at ww, passes through xx and yy, and ends at zz.

Number the vertices arbitrarily from 11 to VV. For every pair of vertices uu and vv and every integer rr, we define a path π(u,v,r)π(u, v, r) as follows:

π(u,v,r)π(u,v,r) is the shortest path (if any) from uu to vv that passes through only vertices numbered at most rr.

In particular, π(u,v,V)π(u,v,V) is the true shortest path from uu to vv. Kleene and Roy and Warshall all observed that these paths have a simple recursive structure.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy