Python program to implement Multistage Graph (Shortest Path)

In this Python programming tutorial, 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={k₁,k₂,……..,k_k} 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 k_i, and v belongs to k_i+1 for some subsets in the partition. Also, |k₁| = |k_k|=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.

EXAMPLE:

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

Below is our Python program for implementing the multistage graph:

#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=[0]*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[0] 
  
# Driver code  
n=9
infinity=sys.maxsize
  
#Adjacency matrix for graph
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(n²).

More To Read:

1. How to Count maximum points on same line in Python
2. Diagonal traversal of a binary tree in Python

One response to “Python program to implement Multistage Graph (Shortest Path)”

1. Vidya says:

   July 27, 2022 at 9:18 pm

   Which method u used in python program dynamic programming, dijkstra’s or greedy method)?

   Reply