Multistage graph problem code using C++

Multistage graph problem code

 

Problem Statement

Finding shortest path for multistage graph problem with single source shortest path and all pairs shortest path.

Definition of Multistage graph

A Multistage graph is a graph which satisfy these conditions :

  • G=(V,E) whereas V partitioned into T >= 2 disjoint subsets in such a way ….. if (a,b) is in E, then a is in Vi , and b is in Vi+1 for some subsets in the partition.
  • and also follow this condition | V1 | = | VT | = 1.

Here you can see vertex S in V1 is known as source of the Graph and the vertex t in VT is Know as the sink of the Graph.The cost of a path from node v to node w is sum of the costs of edges in the path.

In the Above definition G is called as the weighted graph. Multistage graph problem is basically to find the least cost path from Source to Destination .

Multistage graph problem code

 

 

Multistage graph problem code Download