Dynamic Programming: Multistage Graphs

cost (i,j) = minl Vi+1 and (j,l) E {c(j,l) + cost(i+1,l)}
remember, i just says which V it is in
(text definition:cost(i,j) is the cost of the path from vertex j in Vi to vertex t)

cost(4,9) = 4,   cost(4,10) = 2,   cost(4,11) = 5

cost(3,6) = min{ 6 + cost(4,9), 5 + cost(4,10)}
= 7

cost(3,7) = min{ 4 + cost(4,9), 3 + cost(4,10)}
= 5

cost(3,8) = min{ 6 + cost(4,11), 5 + cost(4,10)} }
= 7

cost(2,2) = min{ 4 + cost(3,6), 2 + cost(3,7), 1 + cost(3,8) }
= 7

cost(2,3) = 9

cost(2,4) = min{ 11 + cost(3,8)} = 18

cost(2,5) = 15

cost(1,1) = min{ 9 + cost(2,2), 7 + cost(2,3), 3 + cost(2,4), 2 + cost(2,5) }
= 16

If we reuse the values of calculations we can avoid recomputation. The text shows d(i,j) where i is the V and j is the node that is used to get the minimum.

The path can be determined easily if we record the decision made at each state (vertex) ... i.e, which node provided the minimum cost at each decision.

So d(3,6), d(3,7) and d(3,8) = (or more explicitly, came through) node 10
d(2,2) = node 7   d(2,3) = node 6   d(2,4) = node 8 (only choice here was node 8)   d(2,5) = node 8
d(1,1) = node 2

So, node 1 (in V1) goes to node 2, node 2 (in V2) to node goes to node 7, node 7 (in V3) goes to node 10, and node 10 goes to node 12 (or t)