Go backward to
Observation
Go up to
Top
Go forward to
Time Analysis
Optimization
Instead of computing
W
1
, W
2
, W
3
, ..., W
n-1
we can compute
W
1
, W
2
, W
4
, ..., W
2
s
(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!
Author:
Wolfgang Schreiner
Last modification: November 15, 1996