A multistage graph G=(V,E) which is a directed graph. In this graph all the vertices are partitioned into the k stages where k>=2.

In multistage graph problem we have to find the shortest path from source to sink.

The cost of a path from source (denoted by S) to sink (denoted by T) is the sum of the costs of edges on the path. In multistage graph problem we have to find the path from S to T. there is set of vertices in each stage. The multistage graph can be solved using forward and backward approach. Let us solve multistage problem for both the approaches with the help of example.

Consider the graph G as shown in the figure.

There is a single vertex in stage 1, then 3 vertices in stage 2, then 2 vertices in stage 3 and only one vertex in stage 4 (this is a target stage).

Backward approach

d(S, T)=min {1+d(A, T),2+d(B,T),7+d(C,T)} …(1)

We will compute d(A,T), d(B,T) and d(C,T).

d(A,T)=min{3+d(D,T),6+d(E,T)} …(2)

d(B,T)=min{4+d(D,T),10+d(E,T)} …(3)

d(C,T)=min{3+d(E,T),d(C,T)} …(4)

Now let us compute d(D,T) and d(E,T).

d(D,T)=8

d(E,T)=2 backward vertex=E

Let us put these values in equations (2), (3) and (4)

d(A,T)=min{3+8, 6+2}

d(A,T)=8 A-E-T

d(B,T)=min{4+8,10+2}

d{B,T}=12 A-D-T

d(C,T)=min(3+2,10)

d(C,T)=5 C-E-T

d(S,T)=min{1+d(A,T), 2+d(B,T), 7+d(C,T)}

=min{1+8, 2+12,7+5}

=min{9,14,12}

d(S,T)=9 S-A-E-T

The path with minimum cost is S-A-E-T with the cost 9.

Forward approach

d(S,A)=1

d(S,B)=2

d(S,C)=7

d(S,D)=min{1+d(A,D),2+d(B,D)}

=min{1+3,2+4}

d(S,D)=4

d(S,E)=min{1+d(A,E), 2+d(B,E),7+d(C,E)}

=min {1+6,2+10,7+3}

=min {7,12,10}

d(S,E)=7 i.e. Path S-A-E is chosen.

d(S,T)=min{d(S,D)+d(D,T),d(S,E),d(E,T),d(S,C)+d(C,T)}

=min {4+8,7+2,7+10}

d(S,T)=9 i.e. Path S-E, E-T is chosen.

The minimum cost=9 with the path S-A-E-T.

Using dynamic approach programming strategy, the multistage graph problem is solved. This is because in multistage graph problem we obtain the minimum path at each current stage by considering the path length of each vertex obtained in earlier stage.

Thus the sequence of decisions is taken by considering overlapping solutions. In dynamic programming, we may get any number of solutions for given problem. From all these solutions we seek for optimal solution, finally solution becomes the solution to given problem. Multistage graph problem is solved using this same approach.