Project ForgeThere are multiple routes to reach from node 1 to node 2 in a network. Edge travel costs (in rupees): 1-a=200, 1-b=300, 1-f=100, a-c=100, a-2=200, c-2=100, b-2=200, f-b=0, b-d=0, d-e=100, e-2=200, f-e=100. Nodes 'a', 'b', 'c', 'd', 'e', and 'f' are toll booths. The toll price at toll booths 'a' and 'e' is Rs. 200, and Rs. 100 for the other toll booths ('b', 'c', 'd', 'f'). Which is the cheapest route from node 1 to node 2?
- A1-a-c-2
- 1-f-b-2
- C1-b-2
- D1-f-e-2
Explanation
Total cost = sum of edge travel costs + toll charged at every toll-booth node visited (not counting nodes 1 and 2 themselves). Route 1-a-c-2: travel 200+100+100=400, tolls a(200)+c(100)=300, total 700. Route 1-f-b-2: travel 100+0+200=300, tolls f(100)+b(100)=200, total 500. Route 1-b-2: travel 300+200=500, toll b(100), total 600. Route 1-f-e-2: travel 100+100+200=400, tolls f(100)+e(200)=300, total 700. The cheapest is 1-f-b-2 at Rs. 500.
Source: GATE CS 2020 (2020)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.