Go backward to Example Go up to Top Go forward to Construction

Solution Idea

• Construct sequence of matrices
  • D₀, D₁, ..., 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!