Shortest Paths And Matrix Multiplication
Improving the running time
Our goal, however, is not to compute all the L^{(m)} matrices: we are interested only in matrix L^{(n1)}. Recall that in the absence of negativeweight cycles, equation (25.3) implies L^{(m)} = L^{(n1)} for all integers m ≥ n  1. Just as traditional matrix multiplication is associative, so is matrix multiplication defined by the EXTENDSHORTESTPATHS procedure. Therefore, we can compute L^{(n1)} with only ⌈lg(n  1)⌉ matrix products by computing the sequence
L^{(1)} 
= 
W, 

L^{(2)} 
= 
W^{2} 
= 
W · W, 
L^{(4)} 
= 
W^{4} 
= 
W^{2} · W^{2} 
L^{(8)} 
= 
W^{8} 
= 
W^{4} · W^{4}, 
⋮ 


= 

= 
. 
Since 2^{⌈lg(n1)⌉} ≥ n  1, the final product is equal to L^{(n1)}.
The following procedure computes the above sequence of matrices by using this technique of repeated squaring.
FASTERALLPAIRSSHORTESTPATHS(W) 1 n ← rows[W] 2 L(1) ← W 3 m ← 1 4 while m < n  1 5 do L(2m) ← EXTENDSHORTESTPATHS(L(m), L(m)) 6 m ← 2m 7 return L(m)
In each iteration of the while loop of lines 46, we compute L^{(2m)} = (L^{(m)})^{2}, starting with m = 1. At the end of each iteration, we double the value of m. The final iteration computes L^{(n1)} by actually computing L^{(2m)} for some n  1 ≤ 2m < 2n  2. By equation (25.3), L^{(2m)} = L^{(n1)}. The next time the test in line 4 is performed, m has been doubled, so now m ≥ n  1, the test fails, and the procedure returns the last matrix it computed.
The running time of FASTERALLPAIRSSHORTESTPATHS is Θ(n^{3} lg n) since each of the ⌈lg(n  1)⌉ matrix products takes Θ(n^{3}) time. Observe that the code is tight, containing no elaborate data structures, and the constant hidden in the Θnotation is therefore small.