\"\" \"\" \"\"
Go backward to Solution Idea
Go up to Top
Go forward to Sequential Algorithm
RISC-Linz logo

Construction

D0(i,j) =
0 if i = j
infty if i /=j

D1(i,j) = W(i,j)

Dn+1(i,j) = ?
Two Cases
  1. |p |= n
  2. |p |= n+1
Dn+1(i,j) = min{Dn(i,j),
mink{Dn(i,k)+W(k,j)}}

Author: Wolfgang Schreiner
Last modification: November 15, 1996