# Python program to implement Multistage Graph (Shortest Path)

Here we will learn how to implement a multistage graph in Python (Shortest Path).

A multistage graph is a special type of graph. In this type of graph, we partition the vertices into k number of disjoint subsets. Let K={k1,k2,……..,kk} be the set of these disjoint subsets. We represent the graph as G=(V, E). The k subsets are divided such that edge (u,v) is in E, then u belongs to ki, and v belongs to ki+1 for some subsets in the partition. Also, |k1| = |kk|=1.  The first vertex of the graph is called source while the last vertex is known as the sink.

Hence, a multistage graph is a type of graph in which we divide nodes into parts or stages and all edges are from a stage to the next stage only.

The problem at hand is given a multistage graph we need to find the shortest distance from the source of the graph to the sink. We know, in a multistage graph source is at stage 1 and the sink is at the last stage. Hence, we need to find the shortest distance between the first and the last stage.

The method which we are going to apply is recursive in nature. We take the sink as the destination. Let sink is at stage k. We find the shortest path from all nodes at stage k-1 to the sink and select the node which gives this shortest path. Now we store this value. after this in step 2, we define the node selected in step 1 as the destination. Now, we find the shortest path from k-2 to the node selected in step 1. We do this until we reach the source. After every step, we add the value of the shortest path to the previous values. Therefore in the end, what we are left is with the required shortest path value from source to sink.

#### In the above example, we find the shortest path manually using the same algorithm which is discussed above. Now, we try to solve the same problem using python code. Hence, the answer to the shortest path is 19.

## CODE: Multistage Graph (Shortest Path) in Python

```#Python3 program for multistage graph (shortest path).
import sys

#function for finding shortest distance
def Source_to_Sink(MG):
#list for storing shortest distance from particular node to N-1 node
Distance=*n
#finding the shortest paths
for x in range(n-2, -1, -1):
Distance[x]=infinity
#Checking nodes from next stages
for y in range(n):
#condition when no edge exists
if MG[x][y]==infinity:
continue
#finding minimum distances
Distance[x]=min(MG[x][y]+Distance[y],Distance[x])
return Distance

# Driver code
n=9
infinity=sys.maxsize

MG=[[infinity, 10, 5, infinity, infinity, infinity, infinity, infinity, infinity],
[infinity, infinity, infinity, 1, infinity, 2, infinity, infinity, infinity],
[infinity, infinity, infinity, 8, 4, 7,infinity, infinity, infinity],
[infinity, infinity, infinity, infinity, infinity, infinity, 5, 3, infinity],
[infinity, infinity, infinity, infinity, infinity, infinity, 6, 9, infinity],
[infinity, infinity, infinity, infinity, infinity, infinity, 11, 15, infinity],
[infinity, infinity, infinity, infinity, infinity, infinity, infinity, infinity, 4],
[infinity, infinity, infinity, infinity, infinity, infinity, infinity, infinity, 7]]

D=Source_to_Sink(MG)
print("SHORTEST PATH FROM SOURCE TO SINK IS :",D)
print("CODE BY: YATHARTH JAIN")
```

#### OUTPUT:

```SHORTEST PATH FROM SOURCE TO SINK IS : 19
CODE BY: YATHARTH JAIN```

The time complexity of the code is O(n2).