Go backward to
Example
Go up to
Top
Go forward to
Construction
Solution Idea
Construct sequence of matrices
D
0
, D
1
, ..., D
n-1
D
i
describes all shortest paths with not more than
i
edges.
Consequence:
D
n-1
= D
Proof
Assume shortest path
p
with more than
n-1
edges. Then there is some node
v
twice in this path i.e.
p=<i, ...,
v, ..., v
, ..., j >
. But then path
p'=<i, ..., v, ..., j >
is shorter!
Author:
Wolfgang Schreiner
Last modification: November 15, 1996