# Multistage Graph (Shortest Path)

A Multistage graph is a directed graph in which the nodes can be divided into a set of stages such that all edges are from a stage to next stage only (In other words there is no edge between vertices of same stage and from a vertex of current stage to previous stage).

We are give a multistage graph, a source and a destination, we need to find shortest path from source to destination. By convention, we consider source at stage 1 and destination as last stage.

Following is an example graph we will consider in this article :-

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Now there are various strategies we can apply :-

• The Brute force method of finding all possible paths between Source and Destination and then finding the minimum. That’s the WORST possible strategy.
• Dijkstra’s Algorithm of Single Source shortest paths. This method will find shortest paths from source to all other nodes which is not required in this case. So it will take a lot of time and it doesn’t even use the SPECIAL feature that this MULTI-STAGE graph has.
• Simple Greedy Method – At each node, choose the shortest outgoing path. If we apply this approach to the example graph give above we get the solution as 1 + 4 + 18 = 23. But a quick look at the graph will show much shorter paths available than 23. So the greedy method fails !
• The best option is Dynamic Programming. So we need to find Optimal Sub-structure, Recursive Equations and Overlapping Sub-problems.

Optimal Substructure and Recursive Equation :-

We define the notation :- M(x, y) as the minimum cost to T(target node) from Stage x, Node y.

Shortest distance from stage 1, node 0 to
destination, i.e., 7 is M(1, 0).

// From 0, we can go to 1 or 2 or 3 to
// reach 7.
M(1, 0) = min(1 + M(2, 1),
2 + M(2, 2),
5 + M(2, 3))

This means that our problem of 0 —> 7 is now sub-divided into 3 sub-problems :-

So if we have total 'n' stages and target
as T, then the stopping condition  will be :-
M(n-1, i) = i ---> T + M(n, T) = i ---> T

Recursion Tree and Overlapping Sub-Problems:-
So, the hierarchy of M(x, y) evaluations will look something like this :-

In M(i, j), i is stage number and
j is node number

M(1, 0)
/          |
/           |
M(2, 1)      M(2, 2)        M(2, 3)
/              /              /
M(3, 4)  M(3, 5)  M(3, 4)  M(3, 5) M(3, 6)  M(3, 6)
.         .       .       .          .        .
.         .       .       .          .        .
.         .       .       .          .        .

So, here we have drawn a very small part of the Recursion Tree and we can already see Overlapping Sub-Problems. We can largely reduce the number of M(x, y) evaluations using Dynamic Programming.

Implementation details:
The below implementation assumes that nodes are numbered from 0 to N-1 from first stage (source) to last stage (destination). We also assume that the input graph is multistage.

## C++

 // CPP program to find shortest distance // in a multistage graph. #include using namespace std;    #define N 8 #define INF INT_MAX    // Returns shortest distance from 0 to // N-1. int shortestDist(int graph[N][N]) {        // dist[i] is going to store shortest     // distance from node i to node N-1.     int dist[N];        dist[N-1] = 0;        // Calculating shortest path for     // rest of the nodes     for (int i = N-2 ; i >= 0 ; i--)     {            // Initialize distance from i to         // destination (N-1)         dist[i] = INF;            // Check all nodes of next stages         // to find shortest distance from         // i to N-1.         for (int j = i ; j < N ; j++)         {             // Reject if no edge exists             if (graph[i][j] == INF)                 continue;                // We apply recursive equation to             // distance to target through j.             // and compare with minimum distance              // so far.             dist[i] = min(dist[i], graph[i][j] +                                         dist[j]);         }     }        return dist[0]; }    // Driver code int main() {     // Graph stored in the form of an     // adjacency Matrix     int graph[N][N] =       {{INF, 1, 2, 5, INF, INF, INF, INF},        {INF, INF, INF, INF, 4, 11, INF, INF},        {INF, INF, INF, INF, 9, 5, 16, INF},        {INF, INF, INF, INF, INF, INF, 2, INF},        {INF, INF, INF, INF, INF, INF, INF, 18},        {INF, INF, INF, INF, INF, INF, INF, 13},        {INF, INF, INF, INF, INF, INF, INF, 2}};        cout << shortestDist(graph);     return 0; }

## Python3

# Python3 program to find shortest
# distance in a multistage graph.

# Returns shortest distance from
# 0 to N-1.
def shortestDist(graph):
global INF

# dist[i] is going to store shortest
# distance from node i to node N-1.
dist = [0] * N

dist[N – 1] = 0

# Calculating shortest path
# for rest of the nodes
for i in range(N – 2, -1, -1):

# Initialize distance from
# i to destination (N-1)
dist[i] = INF

# Check all nodes of next stages
# to find shortest distance from
# i to N-1.
for j in range(N):

# Reject if no edge exists
if graph[i][j] == INF:
continue

# We apply recursive equation to
# distance to target through j.
# and compare with minimum
# distance so far.
dist[i] = min(dist[i],
graph[i][j] + dist[j])

return dist[0]

# Driver code
N = 8
INF = 999999999999

# Graph stored in the form of an
graph = [[INF, 1, 2, 5, INF, INF, INF, INF],
[INF, INF, INF, INF, 4, 11, INF, INF],
[INF, INF, INF, INF, 9, 5, 16, INF],
[INF, INF, INF, INF, INF, INF, 2, INF],
[INF, INF, INF, INF, INF, INF, INF, 18],
[INF, INF, INF, INF, INF, INF, INF, 13],
[INF, INF, INF, INF, INF, INF, INF, 2]]

print(shortestDist(graph))

# This code is contributed by PranchalK

## C#

 // C# program to find shortest distance  // in a multistage graph. using System;       class GFG  {      static int N = 8;      static int INF = int.MaxValue;               // Returns shortest distance from 0 to      // N-1.      public static int shortestDist(int[,] graph) {                   // dist[i] is going to store shortest          // distance from node i to node N-1.          int[] dist = new int[N];                   dist[N-1] = 0;                   // Calculating shortest path for          // rest of the nodes          for (int i = N-2 ; i >= 0 ; i--)          {                       // Initialize distance from i to              // destination (N-1)              dist[i] = INF;                       // Check all nodes of next stages              // to find shortest distance from              // i to N-1.              for (int j = i ; j < N ; j++)              {                  // Reject if no edge exists                  if (graph[i,j] == INF)                      continue;                           // We apply recursive equation to                  // distance to target through j.                  // and compare with minimum distance                   // so far.                  dist[i] = Math.Min(dist[i], graph[i,j] +                                              dist[j]);              }          }                   return dist[0];      }               // Driver code      static void Main()      {          // Graph stored in the form of an          // adjacency Matrix          int[,] graph = new int[,]            {{INF, 1, 2, 5, INF, INF, INF, INF},             {INF, INF, INF, INF, 4, 11, INF, INF},             {INF, INF, INF, INF, 9, 5, 16, INF},             {INF, INF, INF, INF, INF, INF, 2, INF},             {INF, INF, INF, INF, INF, INF, INF, 18},             {INF, INF, INF, INF, INF, INF, INF, 13},             {INF, INF, INF, INF, INF, INF, INF, 2}};                   Console.Write(shortestDist(graph));     }     //This code is contributed by DrRoot_ }

Output:

9

Time Complexity : O(n2)