Trusted answers to developer questions

Aarthi

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: $cost(i,j)=min{c(j,l)+cost(i+1,l)}$

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
```

RELATED TAGS

general

communitycreator

CONTRIBUTOR

Aarthi

RELATED COURSES

View all Courses

Keep Exploring

Related Courses