Algorithm
-
Getting Started with AlgorithmWhat is an Algorithm?
-
Characteristics of Algorithm1 Topic
-
Analysis Framework
-
Performance Analysis3 Topics
-
Mathematical Analysis2 Topics
-
Sorting AlgorithmSorting Algorithm10 Topics
-
Searching Algorithm6 Topics
-
Fundamental of Data StructuresStacks
-
Queues
-
Graphs
-
Trees
-
Sets
-
Dictionaries
-
Divide and ConquerGeneral Method
-
Binary Search
-
Recurrence Equation for Divide and Conquer
-
Finding the Maximum and Minimum
-
Merge Sort
-
Quick Sort
-
Stassen’s Matrix Multiplication
-
Advantages and Disadvantages of Divide and Conquer
-
Decrease and ConquerInsertion Sort
-
Topological Sort
-
Greedy MethodGeneral Method
-
Coin Change Problem
-
Knapsack Problem
-
Job Sequencing with Deadlines
-
Minimum Cost Spanning Trees2 Topics
-
Single Source Shortest Paths1 Topic
-
Optimal Tree Problem1 Topic
-
Transform and Conquer Approach1 Topic
-
Dynamic ProgrammingGeneral Method with Examples
-
Multistage Graphs
-
Transitive Closure1 Topic
-
All Pairs Shortest Paths6 Topics
-
BacktrackingGeneral Method
-
N-Queens Problem
-
Sum of Subsets problem
-
Graph Coloring
-
Hamiltonian Cycles
-
Branch and Bound2 Topics
-
0/1 Knapsack problem2 Topics
-
NP-Complete and NP-Hard Problems1 Topic
Participants2253
Multistage Graphs
A multistage graph G = (V, E) is a directed graph where vertices are partitioned into k (where k > 1) number of disjoint subsets S = {s1,s2,…,sk} such that edge (u, v) is in E, then u Є si and v Є s1 + 1 for some subsets in the partition and |s1| = |sk| = 1.
The vertex s Є s1 is called the source and the vertex t Є sk is called sink.
G is usually assumed to be a weighted graph. In this graph, cost of an edge (i, j) is represented by c(i, j). Hence, the cost of path from source s to sink t is the sum of costs of each edges in this path.
The multistage graph problem is finding the path with minimum cost from source s to sink t.
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.
Algorithm for Backward Approach
1. Algorithm BGraph (G, K, n, p)
2. // some function as FGraph
3. {
4. B cost [1] = 0.0;
5. For j = 2 to n do
6. {
7. // compute b cost [j].
8. Let r be such that is an edge of
9. G and b cost [r] + c [r, j];
10. D [j] = r;
11. }
12. // find a minimum cost path
13. P [1] = 1; p [k] = n;
14. For j = k-1 to 2 do p[j] = d [p (j+1)];
15. }
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.
Algorithm for Forward Approach
1. F graph (graph G, int K, int n, int p[])
2. {
3. Float cost [max size], int d [max size], r;
4. Cost [n] = 0.0
5. For (int j = n-1; j>= 1; j--)
6. {
7. Let r be a vertex such that is an edge of G and C[j][r] + cost[r]
is minimum;
8. Cost [j] = C[j][r] + Cost[r]
9. D [j] = r
10. }
11. P [1] = 1 , P[k] = n
12. For (j = 2 ; j <= K-1; j++)
13. P[j] = d[P(j-1)];
14. }
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.

