\"\" \"\" \"\"
Go backward to Observation
Go up to Top
Go forward to Time Analysis
RISC-Linz logo

Optimization

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!
Author: Wolfgang Schreiner
Last modification: November 15, 1996