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.

The strategies that can be used are:

- Brute force method
- Dijkstraโs Algorithm
- Simple Greedy Method
- Dynamic Programming

**Implementation**

```
// 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));
}
}
```

**Output**

```
9
```

**Time Complexity**

O(n^2)

## Top comments (0)