Back to Course

Algorithm

0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
    Stacks
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
Lesson 33 of 43
In Progress

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.

enter image description here

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.

KodNest Capture67
Figure 5: Five-stage graph
KodNest Capture68
Figure 6: Four-stage graph corresponding to a three-project problem

New Report

Close