Shortest Paths And Matrix Multiplication

Figure 25.1: A directed graph and the sequence of matrices L^(m) computed by SLOW-ALL-PAIRS-SHORTEST-PATHS. The reader may verify that L⁽⁵⁾ = L⁽⁴⁾ · W is equal to L⁽⁴⁾, and thus L^(m) = L⁽⁴⁾ for all m ≥ 4.

Improving the running time

Our goal, however, is not to compute all the L^(m) matrices: we are interested only in matrix L^(n-1). Recall that in the absence of negative-weight cycles, equation (25.3) implies L^(m) = L^(n-1) for all integers m ≥ n - 1. Just as traditional matrix multiplication is associative, so is matrix multiplication defined by the EXTEND-SHORTEST-PATHS procedure. Therefore, we can compute L^(n-1) with only ⌈lg(n - 1)⌉ matrix products by computing the sequence

L⁽¹⁾	=	W,
L⁽²⁾	=	W²	=	W · W,
L⁽⁴⁾	=	W⁴	=	W² · W²
L⁽⁸⁾	=	W⁸	=	W⁴ · W⁴,
		⋮
	=		=	.

Since 2^{⌈lg(n-1)⌉} ≥ n - 1, the final product is equal to L^(n-1).

The following procedure computes the above sequence of matrices by using this technique of repeated squaring.

		FASTER-ALL-PAIRS-SHORTEST-PATHS(W)
1  n ← rows[W]
2  L(1) ← W
3  m ← 1
4  while m < n - 1
5      do L(2m) ← EXTEND-SHORTEST-PATHS(L(m), L(m))
6         m ← 2m
7  return L(m)

In each iteration of the while loop of lines 4-6, we compute L^(2m) = (L^(m))², starting with m = 1. At the end of each iteration, we double the value of m. The final iteration computes L^(n-1) by actually computing L^(2m) for some n - 1 ≤ 2m < 2n - 2. By equation (25.3), L^(2m) = L^(n-1). 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 FASTER-ALL-PAIRS-SHORTEST-PATHS is Θ(n³ lg n) since each of the ⌈lg(n - 1)⌉ matrix products takes Θ(n³) time. Observe that the code is tight, containing no elaborate data structures, and the constant hidden in the Θ-notation is therefore small.