Go backward to Observation Go up to Top Go forward to Time Analysis

Optimization

• Instead of computing
  • W¹, W², W³, ..., W^n-1
• we can compute
  • W¹, W², W⁴, ..., W^2s
    (where 2^s >= n-1).

AllPairsShortestPaths(W):
  D = W
  for i=1 to s do
    D = MatMin(D, D)
  return D

We can reduce n matrix multiplications to log n square computations!