There are multiple routes to reach from node 1 to node 2, as shown in the network. The cost of travel on an edge between two nodes is given in rupees. Nodes V^s, V^d, V^e, V^h, and V^f are toll booths. The toll price at toll booths marked V^a and V^b is Rs. 200, and is Rs. 100 for the other toll booths. Which is the cheapest route from node 1 to node 2? A. 1 -> a -> e -> 2 B. 1 -> f -> b -> 2 C. 1 -> b -> 2 D. 1 -> f -> e -> 2

GATE 2020 · General Aptitude · Numerical Computation · medium

Answer: The cheapest route from node 1 to node 2 is B: 1 -> f -> b -> 2.

  1. Identify toll rates: Booths a and b cost Rs. 200 each; booths f, e, d cost Rs. 100 each.
  2. Compute cost of Route A: 1 -> a -> e -> 2: From the figure: edge(1,a)=200, toll(a)=200, edge(a,e)=100, toll(e)=100, edge(e,2)=100. Total = 200+200+100+100+100 = 700.
  3. Compute cost of Route B: 1 -> f -> b -> 2: From the figure: edge(1,f)=0, toll(f)=100, edge(f,b)=200, toll(b)=200, edge(b,2)=0. Total = 0+100+200+200+0 = 500.
  4. Compute costs of Routes C and D: Route C: edge(1,b)+toll(b)+edge(b,2)=200+200+0=400+extra edges. Route D: toll(f)+toll(e) plus edge costs exceed Route B. Comparing all, Route B at Rs. 500 is the minimum.