Skip to content
GATEiit

GATE CSE 2020 Q5: Cheapest route through a network with edge costs and tolls

Question

There are multiple routes to reach from node 1 to node 2, as shown in the network.

Directed network from node 1 to node 2 through nodes a to f: 1→a 200, 1→b 300, 1→f 100, a→c 100, a→2 200, c→2 100, b→2 200, b→d 0, f→b 0, d→e 100, f→e 100, e→2 200
Tap the figure to enlarge

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?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: B (official GATE 2020 final answer key)

Concept used: Route cost = sum of edge costs plus the toll at every booth passed through.

First step: Price each option: for 1-f-b-2 it is 100 + 100 (toll f) + 0 + 100 (toll b) + 200; compare with the others.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key

More General Aptitude PYQs

PracticePractise General Aptitude questions →Full paperAll GATE CSE 2020 questions →