Let G = (V, E) be a directed, weighted graph with weight function w: E R. For some function f: V R, for each edge (u, v) E, define w'(u, v) as 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 G under w are shortest paths under w' too, … ”. A) for every f: V R B) if and only if u V,\ f(u) is positive C) if and only if u V,\ f(u) is negative D) if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G

Official answer: A) for every f: V R. Explanation: Let P = (v0, v1, v2, , vk) be any directed path from vertex u = v0 to vertex v = vk. The total weight of path P under the modified weight function w' is given by the telescoping sum: w'(P) = i=1k w'(vi-1, vi) = i=1k [w(vi-1, vi) + f(vi-1) - f(vi)] w'(P) = i=1k w(vi-1, vi) + [f(v0) - f(v1) + f(v1) - f(v2) + + f(vk-1) - f(vk)] w'(P) = w(P) + f(u) - f(v) Notice that the extra term f(u) - f(v) depends solely on the source u and target v, and is identical for all paths between u and v. Adding a constant value to every path between u and v does not change their relative ordering in weight. Therefore, a path between u and v minimizes w(P) if and only if it minimizes w'(P). This property holds for every function f: V R, making A the correct choice (this is the reweighting technique used in Johnson's algorithm).

B) if and only if u V,\ f(u) is positive

C) if and only if u V,\ f(u) is negative

D) if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G

Algorithms · Shortest Paths

Official IIT answer key · IIT Delhi · Audited Aug 2026

Take topic test

GATE CSE 2020 Q40 · MCQ · 2 marks

Let $G = (V, E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$ . For some function $f: V \rightarrow \mathbb{R}$ , for each edge $(u, v) \in E$ , define $w^{\prime}(u, v)$ as $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 $G$ under $w$ are shortest paths under $w^{\prime}$ too, ___________”.

Select an option to check

Key concept

Shortest Paths

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Shortest Paths

Shortest paths questions in GATE CS consistently assess both procedural graph execution (exact state transitions during relaxation under explicit tie-breaking conditions) and deep structural properties of shortest path algorithms. Across the years, the topic spans algorithm tracing (Dijkstra), graph reweighting principles (Johnson's technique), parametric weight constraints, and optimal algorithmic bounds on specialized topologies (such as DAGs). Questions are invariably weighted at 2 marks, reflecting high conceptual and analytical rigor.

Full Shortest Paths guide →

More on Shortest Paths

All 4 questions on Shortest Paths →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Algorithms · Shortest Paths

Official IIT answer key · IIT Delhi · Audited Aug 2026

Take topic test

GATE CSE 2020 Q40 · MCQ · 2 marks

Let $G = (V, E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$ . For some function $f: V \rightarrow \mathbb{R}$ , for each edge $(u, v) \in E$ , define $w^{\prime}(u, v)$ as $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 $G$ under $w$ are shortest paths under $w^{\prime}$ too, ___________”.

Select an option to check

Key concept

Shortest Paths

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Shortest Paths

Full Shortest Paths guide →

More on Shortest Paths

All 4 questions on Shortest Paths →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Step-by-step verified solution

Check you can still solve Shortest Paths under a clock

More from GATE CSE 2020

More on Shortest Paths

Step-by-step verified solution

Check you can still solve Shortest Paths under a clock

More from GATE CSE 2020

More on Shortest Paths

Step-by-step verified solution

Check you can still solve Shortest Paths under a clock

More from GATE CSE 2020

More on Shortest Paths

Share this solution

Step-by-step verified solution

Check you can still solve Shortest Paths under a clock

More from GATE CSE 2020

More on Shortest Paths

Share this solution