A multistage graph G=(V, E) is a directed and weighted graph in which vertices are divided into stages (the first stage and last stage of which will have a single vertex to represent the starting vertex or ending vertex). In between the starting and ending vertex, there will vertices in different stages that connect the starting and ending vertex. The main aim of this graph is to find the minimum cost path between starting and ending vertex.
Consider the following example graph to further understand the multistage graph:
In the above graph, cost of an edge is represented as c(i, j). We need to find the minimum cost path from vertex 1 to vertex 12. Using the below formula we can find the shortest cost path from source to destination:
Step 1 uses the forwarded approach
(cost(5,12) = 0 ).
Here, 5 represents the stage number and 12 represents a node in that stage. Since there are no outgoing edges from vertex 12, the cost is 0.
cost(4,9)=c(9,12)=6
cost(4,10)=c(10,12)=4 cost(4,11)=c(11,12)= 2
cost(3,5)=min{c(5,9)+cost(4,9),c(5,10)+cost(4,10)}
min{5+6,2+4}
min{11,6}=6
cost(3,5)=6
cost(3,6)=min{c(6,10)+cost(4,10),c(6,11)+cost(4,11)}
min{4+4,8+2}
min{8,10}=8
cost(3,6)=8
cost(3,7)=min{c(7,9)+cost(4,9),c(7,10)+cost(4,10),c(7,11)+cost(4,11)} min{7+6,5+4,3+2}
min{13,9,5}=5
cost(3,7)=5
cost(3,8)=c(8,11)+cost(4,11)=7+2=9 cost(3,8)=9
cost(2,2)=min{c(2,5)+cost(3,5),c(2,6)+cost(3,6),c(2,7)+cost(3,7)} min{3+6,5+8,6+5}
min{9,13,11}=9
cost(2,2)=9
cost(2,3)=min{c(3,6)+cost(3,6),c(3,7)+cost(3,7),c(3,8)+cost(3,8)}
min{4+8,5+5,7+9}
min{12,10,16}=10
cost(2,3)=10
cost(2,4)=min{c(4,7)+cost(3,7),c(4,8)+cost(3,8)}
min{2+5,7+9}
min{7,16}=7
cost(2,4)=7
cost(1,1)=min{c(1,2)+cost(2,2),c(1,3)+cost(2,3),c(1,4)+cost(2,4)} min{9+9,7+10,5+7}
min {18,17,12}=12
cost(1,1)=12
From the above calculations we get:
Therefore:
d[1]=4
d[4]=7
d[7]=11
d[11]=12
shortest path 1--4--7--11--12 i.e 12