Improvement of Floyd-Warshall Algorithm

Efficient shortest paths with restricted intermediate vertices

Our fast dynamic programming algorithm is still a factor of $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 $w\rightarrow x\rightarrow y\rightarrow z$ starts at $w$, passes through $x$ and $y$, and ends at $z$.

Number the vertices arbitrarily from $1$ to $V$. For every pair of vertices $u$ and $v$ and every integer $r$, we define a path $π(u, v, r)$ as follows:

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

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