Skip to content
GATEiit

GATE CSE 2020 Q50: Shortest paths under the reweighting w'(u,v) = w(u,v) + f(u) − f(v)

Question

Let G=(V,E)G = (V, E) be a directed, weighted graph with weight function w:E→Rw : E \to \mathbb{R}. For some function f:V→Rf : V \to \mathbb{R}, for each edge (u,v)∈E(u, v) \in E, define w′(u,v)w'(u, v) as w(u,v)+f(u)−f(v)w(u, v) + f(u) - f(v).

Which one of the options completes the following sentence so that it is TRUE?

"The shortest paths in GG under ww are shortest paths under w′w' too, __________".

Try it: multiple choice: exactly one correct option

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

Answer: A (official GATE 2020 final answer key)

Concept used: Potential reweighting (as in Johnson's algorithm): the terms telescope along any path.

First step: Sum w′w' along a path from ss to tt: the intermediate ff values cancel, leaving w(path)+f(s)−f(t)w(\text{path}) + f(s) - f(t).

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 Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2020 questions →