Go backward to Solution Idea Go up to Top Go forward to Sequential Algorithm |
D0(i,j) =
0 if i = j infty if i /=j
D1(i,j) = W(i,j)
Dn+1(i,j) = ?
Two Cases
<i, ..., j> |
n edges |
<i, ..., k, j> |
n edges |
Dn+1(i,j) = min{Dn(i,j), mink{Dn(i,k)+W(k,j)}}