Multistage Graph | Dynamic Programming | ADA

Multistage Graph Problem

This problem is solve by using dynamic programming method. Multistage Graph is a directed weighted graph. All vertices are divided into stages in such a way that vertex are connected to one edge to another edge.Note first stage and last stage are represented as a single vertex from source and sink of a graph.

Let we understand the working of multistage graph problem by the help of example.

This problem is solved by using tabular method , So we draw a table contain all vertices(v) , cost(c) and destination (d).

Here our main objective is to select those path which have minimum cost.So we can say that it is an minimization problem. It can be solved by the principle of optimal which says the sequence of decisions.That means in every stage we have to take decision.

in this problem we will start from 12 so its distance is 12  and cost is 0.

Now calculate for V(12) and stage 5.

here cost( 5 , 12) = 0    I.e Cost( stage number , vertex)

Now update distance and cost in table for stage 5

Now calculate for V(9 ,10 ,11) and stage 4.

cost(4 , 9)  =4

cost(4 , 10) =2

cost(4 , 11) =5

here the distance is 12

So update the new cost and distance in table for stage 4

Now calculate for V(6 , 7 , 8) and stage 3.

For calculating v(6) we must find out there connecting link in previous stage i.e 4. which is 9 and 10.

cost(v,d) + cost(stage+1,vs) , where vs; vertices of that stage.

For v(6)

cost(6,9) + cost(4,9)     

cost(6,10) + cost(4,10)

6 + 4  = 10

5 + 2 =  7

min[10 , 7]

Now we find minimum from [10 , 7] which is 7 and the vertex give the minimum cost is 10.

For v(7)

cost(7,9) + cost(4,9)

cost(7,10) + cost(4,10)

4 + 4 = 8

3 + 2 = 5

min[8 , 5]

Now we find minimum from [8 , 5] which is 5 and the vertex give the minimum cost is 10.

For v(8)

cost(8,10) + cost(4,10)

cost(8,11) + cost(4,11)

5 + 2 = 7

6 + 5 = 11

min[7,11]

Now we find minimum from [7,11] is 7 and the vertex given the minimum cost is 10.

So Now update the new cost and distance in table for stage 3

Now calculate for V(2 , 3 , 4 , 5) and stage 2.

For calculating v(2) we must find out there connecting link in previous stage i.e 3. which is 6 , 7 and 8.

cost(v,d) + cost(stage+1,vs) , where vs; vertices of that stage.

For v(2) find cost(stage,vertex) i.e cost(2,2)

cost(2,6) + cost(3,6)

cost(2,7) + cost(3,7)

cost(2,8) + cost(3,8)

4 + 7 = 11

2 + 5 = 7

1 + 7 = 8

min[11,7,8]

Now we find minimum from [11,7,8] is 7 and the vertex given the minimum cost is 7.

For v(3) find cost(stage,vertex) i.e cost(2,3)

cost(3,6) + cost(3,6)

cost(3,7) + cost(3,7)

2 + 7 = 9

7 + 5 = 12

min[9,12]

Now we find minimum from [9,12] is 9 and the vertex given the minimum cost is 6

For v(4) find cost(stage,vertex) i.e cost(2,4)

cost(4,8) + cost(3,8)

11+ 7 = 18

So here the cost is 18 and the vertex given the minimum cost is 8.

For v(5) find cost(stage,vertex) i.e cost(2,5)

cost(5,7) + cost(3,7)

cost(5,8) + cost(3,8)

11 + 5 = 16

8 + 7 = 15

min[16,15]

Now we find minimum from [16,15] is 15 and the vertex given the minimum cost is 8

So Now update the new cost and distance in table for stage 2.

Now calculate for V(1) and stage 1.

For calculating v(1) we must find out there connecting link in previous stage i.e 2. which is 2 , 3 , 4  and 5.

cost(v,d) + cost(stage+1,vs) , where vs; vertices of that stage.

For v(1) find cost(stage,vertex) i.e cost(1,1)

cost(1,2) + cost(2,2)

cost(1,3) + cost(2,3)

cost(1,4) + cost(2,4)

cost(1,5) + cost(2,5)

9 + 7 =16

7 + 9 =16

3 + 18 = 21

2 + 15 = 17

min[16,16,21,17]

Now we find minimum from [16,16,21,17] is 16 and the vertex given the minimum cost is 2,3 because here we get 16 twice so we consider both vertices.

So Now update the new cost and distance in table for stage 1.

Note: Formula used for calculating cost for any stage.

Where x=stage number   , y=current vertex number  v=vertex of stage x+1.

Now we apply dynamic programming, we know dynamic programming is a sequence of decision on the basis of available data.

Now here data is available in the above table.

For solving let we start from vertex 1 to onward.Here decision is taken in forward direction.

First we find d(stage,vertex) fro taking decision such as

here for 1 we have two value of d 2/3 so we will take 2 first

d(1,1) = 2

d(2,2) = 7

d(3,7) = 10

d(4,10)= 12

so now we can say that the shortest path will be : 2→7→10→12

Now we take decision by taking 3 for vertex 1.

d(1,1) =3

d(2,3) = 6

d(3,6) = 10

d(4,10) =12

so now we can say that the shortest path will be : 3→6→10→12

Here we will consider or select only one option but here we have two path it is optional.