Multistage graph unit 4 of algorithm.ppt

This ppt is about multistage graph

1. Multi-stage Graph …………………………………..

2. <……......?..........> Multistage Graph Algorithm for Mutistage graph Example problem

3. Multi-stage Graph : A multistage 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.

4. Key characteristic of Multistage Graph Stages : The graph is divided into several stages (or levels), each containing a subset of the graph's nodes. Directed Edges : Edges are directed and connect nodes from one stage to the next, not within the same stage. Source and Sink Nodes : There is typically a source node at the first stage and a sink node at the last stage. Pathfinding : The goal is often to find the shortest or longest path from the source to the sink, considering various costs associated with the edges.

5. Notations G =( V , E ) : Multistage graph with vertices 𝑉 V and edges 𝐸 E . c ( i , j ) : Cost of edge from node 𝑖 i to node 𝑗 j . 𝑑(𝑖) d ( i ): Minimum cost to reach the sink from node 𝑖 i . n : Number of stages. s : Source node. t : Sink node.

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,𝑠]=0 d [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. Termination 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. 1 3 2 4 5 6 7 1 4 18 2 9 11 13 5 16 2 5 2 S2 S1 S3 S4

9. 1 3 2 4 5 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C D 7

10. 1 3 2 4 5 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C D 7 C(S.NO,V.NO) S4

11. 1 3 2 4 5 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 18 13 12 D 7 7 7 7 C(S.NO,V.NO) C(3,4) = 18 C(3,5) = 13 C(3,6) = 12 S4 S3

12. 1 3 2 4 5 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 22 18 13 12 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 S4 S3 S2

13. 1 3 2 4 5 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 22 22 18 13 12 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 S3 S4 S2

14. 1 3 2 4 5 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 22 22 14 18 13 12 D 2 5 6 7 7 7 7 C(2,3) = min{ (3,16) + (3,6) } = min{ 2 + 12 } = 14 S4 S3 S2

15. 1 3 2 4 5 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 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 S4 S3 S2 S1

16. 1 3 2 4 5 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 D 3 2 5 6 7 7 7 7 S4 S3 S2 S1 D(0,0) = 3

17. 1 3 2 4 5 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 D 3 2 5 6 7 7 7 7 S4 S3 S2 S1 D(0,0) = 3 D(1,3) = 6

18. 1 3 2 4 5 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 D 3 2 5 6 7 7 7 7 S4 S3 S2 S1 D(0,0) = 3 D(1,3) = 6 D(2,6) = 7

19. 1 2 4 5 3 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 D 3 2 5 6 7 7 7 7 S4 S3 S2 S1 D(0,0) = 3 D(1,3) = 6 D(2,6) = 7

20. 1 2 4 5 3 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 D 3 2 5 6 7 7 7 7 S4 S3 S2 S1 D(0,0) = 3 D(1,3) = 6 D(2,6) = 7

21. 1 2 4 5 3 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 D 3 2 5 6 7 7 7 7 S4 S3 S2 S1 D(0,0) = 3 D(1,3) = 6 D(2,6) = 7

22. 1 2 4 5 3 6 7 1 4 18 2 9 11 13 5 16 2 5 2 V 1 2 3 4 5 6 7 C 19 22 22 14 18 13 12 D 3 2 5 6 7 7 7 7 S4 S3 S2 S1 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 Pseudocode For Multistage graph

24. # 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)