Download to read offline
![Dynamic Programming Approach Initialization Define an array 𝑑d where 𝑑[𝑖,𝑗],d[i,j] represents the minimum cost to reach node 𝑗j in stage 𝑖i. Set 𝑑[1,𝑠]=0d[1,s]=0 since the cost to reach the source node 𝑠s is zero. Set 𝑑[𝑖,𝑗]=∞d[i,j]=∞ for all other 𝑖i and 𝑗j. Transition Iterate through each stage from 1 to the last stage. For each node 𝑢u in the current stage, update the costs for all nodes 𝑣v in the next stage connected by an edge (𝑢,𝑣)(u,v): 𝑑[𝑖+1,𝑣]=min(𝑑[𝑖+1,𝑣],𝑑[𝑖,𝑢]+𝑐(𝑢,𝑣))d[i+1,v]=min(d[i+1,v],d[i,u]+c(u,v))](https://image.slidesharecdn.com/alg-240607011001-f9429be9/75/Multistage-graph-unit-4-of-algorithm-ppt-6-2048.jpg)
![Terminatio n The value 𝑑[𝑛,𝑡]d[n,t] at the sink node 𝑡t in the last stage 𝑛n will give the minimum cost to reach the sink node from the source node. Algorithm Steps: Initialize: Set the cost of reaching the sink node to zero. Process Nodes Stage by Stage: Start from the stage just before the sink and move backwards to the source. Update Costs: For each node in a stage, compute the cost of reaching the sink through all possible nodes in the next stage. Store the minimum cost.](https://image.slidesharecdn.com/alg-240607011001-f9429be9/75/Multistage-graph-unit-4-of-algorithm-ppt-7-2048.jpg)
![function multistageGraphShortestPath(graph, stages): # graph: a 2D list where graph[i][j] represents the weight of the edge from vertex i to vertex j # stages: a list where stages[i] represents the stage number of vertex i # Number of vertices in the graph n = length(graph) # Initialize distance array to store the minimum cost to reach the last stage from each vertex distance = array of size n initialized with infinity distance[n-1] = 0 # Distance to reach the last vertex from itself is 0 # Initialize path array to store the next vertex in the shortest path path = array of size n initialized with -1 # Process vertices in reverse order from the second last stage to the first stage for i from n-2 to 0 step -1: # For each vertex, consider edges to vertices in the next stage for j from 0 to n-1: if graph[i][j] != infinity: # If there is an edge from i to j if distance[j] + graph[i][j] < distance[i]: distance[i] = distance[j] + graph[i][j] path[i] = j Pseudoco de For Multistag e graph](https://image.slidesharecdn.com/alg-240607011001-f9429be9/75/Multistage-graph-unit-4-of-algorithm-ppt-23-2048.jpg)
![# Reconstruct the shortest path shortestPath = list initialized as empty currentVertex = 0 while currentVertex != -1: append currentVertex to shortestPath currentVertex = path[currentVertex] return shortestPath, distance[0] # Example usage graph = [ [infinity, 1, 2, infinity, infinity, infinity], [infinity, infinity, infinity, 3, 4, infinity], [infinity, infinity, infinity, 6, 5, infinity], [infinity, infinity, infinity, infinity, infinity, 2], [infinity, infinity, infinity, infinity, infinity, 1], [infinity, infinity, infinity, infinity, infinity, infinity] ] stages = [1, 2, 2, 3, 3, 4] shortestPath, cost = multistageGraphShortestPath(graph, stages) print("Shortest Path:", shortestPath) print("Cost:", cost)](https://image.slidesharecdn.com/alg-240607011001-f9429be9/75/Multistage-graph-unit-4-of-algorithm-ppt-24-2048.jpg)
Multistage graph unit 4 of algorithm.ppt
- 3. Multi-stage Graph : Amultistage graph is a directed graph organized into multiple stages, where each stage consists of a set of nodes, and there are directed edges from nodes in one stage to nodes in the next stage. Multistage graphs are used to model processes that go through several phases, where each phase represents a stage, and transitions between stages are represented by directed edges.
- 6. Dynamic Programming Approach Initialization Define an array 𝑑d where 𝑑[𝑖,𝑗],d[i,j] represents the minimum cost to reach node 𝑗j in stage 𝑖i. Set 𝑑[1,𝑠]=0d[1,s]=0 since the cost to reach the source node 𝑠s is zero. Set 𝑑[𝑖,𝑗]=∞d[i,j]=∞ for all other 𝑖i and 𝑗j. Transition Iterate through each stage from 1 to the last stage. For each node 𝑢u in the current stage, update the costs for all nodes 𝑣v in the next stage connected by an edge (𝑢,𝑣)(u,v): 𝑑[𝑖+1,𝑣]=min(𝑑[𝑖+1,𝑣],𝑑[𝑖,𝑢]+𝑐(𝑢,𝑣))d[i+1,v]=min(d[i+1,v],d[i,u]+c(u,v))
- 7. Terminatio n The value𝑑[𝑛,𝑡]d[n,t] at the sink node 𝑡t in the last stage 𝑛n will give the minimum cost to reach the sink node from the source node. Algorithm Steps: Initialize: Set the cost of reaching the sink node to zero. Process Nodes Stage by Stage: Start from the stage just before the sink and move backwards to the source. Update Costs: For each node in a stage, compute the cost of reaching the sink through all possible nodes in the next stage. Store the minimum cost.
- 8.
- 9. 0 1 3 2 4 5 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V 01 2 3 4 5 6 7 C 0 D 7
- 10. 0 1 3 2 4 5 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V 01 2 3 4 5 6 7 C 0 D 7 C(S.NO,V.NO) S 4
- 11. 0 1 3 2 4 5 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V 01 2 3 4 5 6 7 C 18 13 12 0 D 7 7 7 7 C(S.NO,V.NO) C(3,4) = 18 C(3,5) = 13 C(3,6) = 12 S 4 S 3
- 12. 0 1 3 2 4 5 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V 01 2 3 4 5 6 7 C 22 18 13 12 0 D 2 7 7 7 7 C(2,1) = min{ (1,4) + (3,4) , (1,5) + (3,5) } = min{ 4 + 18 , 11 + 13 } = min{ 22 , 24 } = 22 S 4 S 3 S 2
- 13. 0 1 3 2 4 5 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V 01 2 3 4 5 6 7 C 22 22 18 13 12 0 D 2 5 7 7 7 7 C(2,2) = min{ (2,4) + (3,4) , (2,5) + (3,5) , (2,6) + (3,6) } = min{ 11 + 18 , 9 + 13 , 16 + 12 } = min{ 29 , 22 , 28 } = 22 S 3 S 4 S 2
- 14. 0 1 3 2 4 5 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V 01 2 3 4 5 6 7 C 22 22 14 18 13 12 0 D 2 5 6 7 7 7 7 C(2,3) = min{ (3,16) + (3,6) } = min{ 2 + 12 } = 14 S 4 S 3 S 2
- 15. 0 1 3 2 4 5 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V 01 2 3 4 5 6 7 C 19 22 22 14 18 13 12 0 D 3 2 5 6 7 7 7 7 C(1,0) = min{ (0,1) + (2,1) + (0,2) + (2,2) , (0,3) + (2,3) } = min{ 1 + 22 , 2 + 22 , 5 + 14 } = min{ 23 , 24 , 19 } = 19 S 4 S 3 S 2 S 1
- 16. 0 1 3 2 4 5 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V 01 2 3 4 5 6 7 C 19 22 22 14 18 13 12 0 D 3 2 5 6 7 7 7 7 S 4 S 3 S 2 S 1 D(0,0) = 3
- 17. 0 1 3 2 4 5 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V 01 2 3 4 5 6 7 C 19 22 22 14 18 13 12 0 D 3 2 5 6 7 7 7 7 S 4 S 3 S 2 S 1 D(0,0) = 3 D(1,3) = 6
- 18. 0 1 3 2 4 5 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V 01 2 3 4 5 6 7 C 19 22 22 14 18 13 12 0 D 3 2 5 6 7 7 7 7 S 4 S 3 S 2 S 1 D(0,0) = 3 D(1,3) = 6 D(2,6) = 7
- 19. 1 2 4 5 0 3 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V0 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 0 D 3 2 5 6 7 7 7 7 S 4 S 3 S 2 S 1 D(0,0) = 3 D(1,3) = 6 D(2,6) = 7
- 20. 1 2 4 5 0 3 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V0 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 0 D 3 2 5 6 7 7 7 7 S 4 S 3 S 2 S 1 D(0,0) = 3 D(1,3) = 6 D(2,6) = 7
- 21. 1 2 4 5 0 3 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V0 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 0 D 3 2 5 6 7 7 7 7 S 4 S 3 S 2 S 1 D(0,0) = 3 D(1,3) = 6 D(2,6) = 7
- 22. 1 2 4 5 0 3 6 7 1 4 1 8 2 9 11 1 3 5 16 2 5 2 V0 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 0 D 3 2 5 6 7 7 7 7 S 4 S 3 S 2 S 1 D(0,0) = 3 D(1,3) = 6 D(2,6) = 7
- 23. function multistageGraphShortestPath(graph, stages): #graph: a 2D list where graph[i][j] represents the weight of the edge from vertex i to vertex j # stages: a list where stages[i] represents the stage number of vertex i # Number of vertices in the graph n = length(graph) # Initialize distance array to store the minimum cost to reach the last stage from each vertex distance = array of size n initialized with infinity distance[n-1] = 0 # Distance to reach the last vertex from itself is 0 # Initialize path array to store the next vertex in the shortest path path = array of size n initialized with -1 # Process vertices in reverse order from the second last stage to the first stage for i from n-2 to 0 step -1: # For each vertex, consider edges to vertices in the next stage for j from 0 to n-1: if graph[i][j] != infinity: # If there is an edge from i to j if distance[j] + graph[i][j] < distance[i]: distance[i] = distance[j] + graph[i][j] path[i] = j Pseudoco de For Multistag e graph
- 24. # Reconstruct theshortest path shortestPath = list initialized as empty currentVertex = 0 while currentVertex != -1: append currentVertex to shortestPath currentVertex = path[currentVertex] return shortestPath, distance[0] # Example usage graph = [ [infinity, 1, 2, infinity, infinity, infinity], [infinity, infinity, infinity, 3, 4, infinity], [infinity, infinity, infinity, 6, 5, infinity], [infinity, infinity, infinity, infinity, infinity, 2], [infinity, infinity, infinity, infinity, infinity, 1], [infinity, infinity, infinity, infinity, infinity, infinity] ] stages = [1, 2, 2, 3, 3, 4] shortestPath, cost = multistageGraphShortestPath(graph, stages) print("Shortest Path:", shortestPath) print("Cost:", cost)