IAE Academy

GATE 2020 CS GA Q.5: solution and answer

GATE 2020 · CSGA Q.5 · 1 mark · MCQ

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 'a', 'b', 'c', 'd', 'e', and 'f' are toll booths. The toll price at toll booths marked 'a' and 'e' is Rs. 200, and is Rs. 100 for the other toll booths. Which is the cheapest route from node 1 to node 2?

GATE 2020 CS GA question 5: A directed network with circled nodes 1 (far left), a (upper left-centre), b (centre-left), c (upper right-centre), d…Tap to open full size
Figure from the GATE 2020 CS paper. It is part of the question.
Figure description

A directed network with circled nodes 1 (far left), a (upper left-centre), b (centre-left), c (upper right-centre), d (centre-right), e (lower right), f (bottom centre-left) and 2 (right). Edges with printed costs: 1->a 200; 1->b 300; 1->f 100; a->c 100; a->2 200 (long diagonal passing below c); c->2 100; b->2 200; b->d 0; d->e 100; f->b 0 (upward arrow); f->e 100; e->2 200 (upward arrow).

  1. (A)

    1-a-c-2

  2. (B)

    1-f-b-2

  3. (C)

    1-b-2

  4. (D)

    1-f-e-2

Answer and solution

ANSWER

The cheapest route is 1-f-b-2, costing Rs. 500 (option B).

Official answer: BSource: Official answer key, GATE 2020 CS (IIT Delhi)

  1. Cost of a route = sum of the edge costs + the toll at every intermediate node passed. Tolls: a and e are Rs. 200; b, c, d, f are Rs. 100. Nodes 1 and 2 are the end points and carry no toll.

  2. (A) 1-a-c-2: edges ; tolls at a and c ; total Rs. 700.

  3. (B) 1-f-b-2: edges ; tolls at f and b ; total Rs. 500.

  4. (C) 1-b-2: edges ; toll at b ; total Rs. 600.

  5. (D) 1-f-e-2: edges ; tolls at f and e ; total Rs. 700.

  6. The least total is Rs. 500, for route 1-f-b-2, which is option (B).

KEY IDEA

Total cost of a route = edge costs + tolls at the intermediate booths only. Work out each option in full and compare the totals.

WATCH OUT FOR

Leaving out the toll booths and comparing edge costs alone, or charging the toll differently at a and e. Edge costs alone give 300 for option B and 400 for options A and D, which hides the fact that tolls change the totals of C, A and D.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 103 Numerical questions, with notes

More Numerical questions