MultiStage Graph:Dynamic Programming approach

calculate step: Bcost(3,j)

Bcost (3, 6) = min {Bcost (2, 2) + c (2, 6), Bcost (2, 3) + c (3, 6)}

= min {Bcost (2, 2) + 4, Bcost (2, 3) + 2}

=min{ 9+4,7+2}= 9

l  _{min(3, 6)}= 3

Bcost (3, 7) = min {Bcost (2, 2) + c (2, 7), Bcost (2, 3) + c (3, 7)}

                     = min {9 + 2, 7 + 7, 2 + 11} = min {11, 14, 13} = 11

l _{min(3, 7)}= 2

Bcost (3, 8) = min {Bcost (2, 2) + c (2, 8), Bcost (2, 4) + c (4, 8), Bcost (2, 5) + c (5, 8)}

= min {9 + 1, 3 + 11, 2 + 8} = min {10, 14, 10} = 10

l _{min(3, 8)}= 2

calculate step: Bcost(4,j)

Bcost (4, 9) = min {Bcost (3, 6) + c (6, 9), Bcost (3, 7) + c (7, 9)}

                   = min {Bcost (3, 6) + 6, Bcost (3, 7) + 4}

                   = 15

l _{min(4, 9)}= 6

Bcost(4,10)= min { Bcost (3, 6) + c (6, 10),,Bcost (3, 7) + c (7, 10), Bcost (3, 8) + c (8, 10)}

 = min {9 + 5, 11 + 3, 10 + 5} = min {14, 14, 15) = 14

l _{min(4, 10)}= 7

Bcost (4, 11) = min {Bcost (3, 8) + c (8, 11)} = min {Bcost (3, 8) + 6} = min {10 + 6} = 16

l _{min(4, 11)}= 8

calculate step: Bcost(5,j)

Bcost (5, 12) = min {Bcost (4, 9) + c (9, 12), Bcost (4, 10) + c (10, 12), Bcost (4, 11) + c (11, 12)}

                      = min {Bcost (4, 9) + 4, Bcost (4, 10) + 2, Bcost (4, 11) + 5}

Bcost (5, 12) = min {15 + 4, 14 + 2, 16 + 5} = min {19, 16, 21} = 16.

l _{min(5, 12)}= 10

Find min cost path from s to t:

s,V₂,V₃,…Vk-1,t

where s=1 &t=12

find V_k-1 =V₄=d(5,12)=10

find V_k-2=V₃=d(4,d(5,12))=d(4,10)=7

find V_k-3=V₂=d(3, d(4,d(5,12)))=d(3,7)=2

therefore shortest path= 1-2-7-10-12