What is a multistage graph in Python?
A multistage graph is a weighted and directed graph; we partition the vertices of this graph into stages in the form of disjointed subsets. Any vertice cannot have an edge with a vertice belonging to the same or lower stages. The arrows show the direction of the vertice, and the number on the edges represents the weight. The structure of the multistage graph is as follows:
Our goal for the multistage graph is to find the shortest path from the first vertice (also known as the source) to the last vertice (also known as the sink). We can determine the shortest path between the source and sink in many ways. Let's look at two of them.
Greedy method
For this method, we will choose the shortest outgoing path for the first vertex and assume that following this path will be the shortest path for the entire graph. The path taken for this method is as follows:
Looking at the rest of the graph, we can tell that using the greedy method here does not lead to the shortest path. Let's look at the second method to find the shortest path in a multistage graph.
Dynamic programming
The dynamic method finds the minimum path for each vertex, determining the shortest path from source to sink. This is the most optimal method to find the shortest path in a multistage graph. The path taken for this method is as follows:
Code
def shortestPath(graph):n = len(graph)+1X = 9999 # Infinitypath = [X] * npath[n - 1] = 0for i in range(n - 2, -1, -1):for j in range(n):path[i] = min(path[i], path[j] + graph[i][j])return path[0]# mainX = 9999graph = [[X, 1, 3, 7, X, X, X], # Vertex 1[X, X, X, X, 5, X, X], # Vertex 2[X, X, X, X, 9, X, X], # Vertex 3[X, X, X, X, X, 2, X], # Vertex 4[X, X, X, X, X, X, 14], # Vertex 5[X, X, X, X, X, X, 6]] # Vertex 6print("Shortest path from source to sink is:", shortestPath(graph))
Explanation
Line 2: Initialization of n number of vertices.
Line 3: Initialize an attribute to represent infinity.
Line 4: Create a matrix populated by infinity values.
Line 5: Set the last index path as the minimum value (0).
Lines 7–11: For the outer loop, checks the shortest distance of the vertices of the current stage. For the inner loop, check for the shortest path for the vertices belonging to the following stages. Finally, we return the first index of the path.
Line 16: Initialize the adjacency matrix for the graph.
Free Resources