find the shortest path in the multistage graph as follows.

Question

By using the dynamic programming (Forward) method, find the shortest path in the multistage graph as follows!

Summary

In the given question we have to use the dynamic programming (Forward) method. By which we have to find the shortest path in the multistage graph which is given above.

Explanation

In the Forward method, we divide the complete graph into different stages and then find the shortest way to reach each vertex of the stage from its previous stage.
In the above graph, we divide it into 7 stages.

• • Stage 1: 0
  • And Stage 2: 1,2
  • Stage 3: 3,4,5,6
  • Stage 4: 7,8,9
  • And Stage 5: 10,11,12
  • Stage 6: 13,14
  • Stage 7: 15

 

Now, Stage 1 is the starting stage.

Stage 2:

d(0,1) = 5

d(0,2) = 3

For stage 2, we find the minimum distance from the starting point to each of its vertex.

Stage 3:

d(0,3) = d(0,1) + d(1,3)= 5+1=6

d(0,4) = min { d(0,1) + d(1,4) , d(0.2)+d(2,4) }

= min { 5+3, 3+8 }

= min {8.11} = 8

d(0,5) = min { d(0,1) + d(1,5) , d(0.2)+d(2,5) }

= min { 5+6, 3+7 }

= min {11, 10} = 10

d(0,6) = d(0,2) + d(2,6)

= 3+6

= 9

Stage 4 :

d(0,7) = min { d(0,3) + d(5,7) , d(0.4)+d(4,7) }

= min { 6+6, 8+3 }

= min { 12. 11}

= 11

d(0,8) = min { d(0,3) + d(3,8) , d(0.4)+d(4,8), d(0,5)+d(5,8), d(0,6)+d(6,8) }

= min { 6+8, 8+5, 10+3, 9+8 }

= min {14, 13, 13, 17} = 13

d(0,9) = min { d(0,5) + d(5,9) , d(0.6)+d(6,9) }

= min { 10+3, 9+4 }

=13

Similarly, we get minimum distances for all vertex of stage 5 and 6 from the starting stage.

Stage 5:

d(0,10) = { d (0,7) + d(7,10)

= 11+2

=12

d(0,11) = min{ d(0,7) + d(7,11), d (0,8)+ d(8,11, d(0,9) +d(9,11) }

= min { 11+2, 13+1, 13+2 }

= min { 13,14,15 }

=13

d(0,12) = min { d(0,8)+d(8,12), d(0,9)+d(9,12) }

= min {13+2, 13+3 }

= 15

Stage 6:

d(0,13) = min{ d(0,10) + d(10,13), d (0,11)+ d(11, 13), d(0,12) +d(12,13) }

= min { 12+3, 13+5, 15+6 }

= min { 15,18,21 }

=15

d(0,14) = min{ d(0,10) + d(10,14), d(0,11)+d(11,14), d(0,12) + d(12,14) }

= min { 12+5, 13+2, 15+6 }

= min { 17,15,21 }

=15

Stage 7:

d(0,15) = { d(0,13)+ d(13,15), d(0,14)+d(14,15) }

=min { 15+4, 15+3 }

= min{ 19,18 }

=18

Now, we get the shortest path from,
= 0→14→15.
= 0→11→14→15
= 0→7→11→14→15
= 0→4→7→11→14→15
= 0→1→4→7→11→14→15

Sum of path distance is= (5+3+3+2+2+3)= 18.

Thus, we get the minimum path to the last stage from the first stage.

 

Also read, A pointer that points to array in C.