The Floyd-Warshall algorithm for ALL-PAIRS SHORTEST PATHS is shown in Figure 3.30. The only difference between it and the matrix-squaring algorithm we gafve in Section 3.4.3 is that the loop over k is now outside the loops over i and j, rather than being the innermost. Surprisingly, this change means that we no longer need to repeat this process times with an additional outer loop, so the running time is now instead of .

Prove that this algorithm works. Hint: state a loop invariant that holds after running the outer loop k times, and use induction on k.