GATE CS 2020 Q.50 (CS Q.40): Graph Traversals, Topological Sort and Connectivity

Let $G = (V, E)$ be a directed, weighted graph with weight function $w: E \to \mathbb{R}$ . For some function $f: V \to \mathbb{R}$ , for each edge $(u, v) \in 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, _______"

for every $f: V \to \mathbb{R}$

if and only if $\forall u \in V,\; f(u)$ is positive

if and only if $\forall u \in V,\; f(u)$ is negative

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 and solution

Official answer: A
From: Official GATE 2020 answer key

Solution

Analyze how telescoping sums affect the total weight of any path under Johnson's reweighting scheme.

Let $P = \langle v_0, v_1, \dots, v_k \rangle$ be any directed path from vertex $u = v_0$ to vertex $v = v_k$ in $G$ .

Compute the path weight under $w'$ :

w'(P) = \sum_{i=1}^{k} w'(v_{i-1}, v_i) = \sum_{i=1}^{k} [w(v_{i-1}, v_i) + f(v_{i-1}) - f(v_i)]

Using the telescoping property of the sum:

\sum_{i=1}^{k} [f(v_{i-1}) - f(v_i)] = f(v_0) - f(v_k) = f(u) - f(v)

Thus:

w'(P) = w(P) + f(u) - f(v)

Significance of the result:

For any fixed pair of endpoints $u$ and $v$ , the quantity $f(u) - f(v)$ is an identical constant for EVERY path connecting $u$ to $v$ .
Therefore, a path $P$ minimizes $w(P)$ if and only if it minimizes $w'(P) = w(P) + f(u) - f(v)$ .
This holds for every function $f: V \to \mathbb{R}$ , without needing any positivity, negativity, or shortest-path distance constraints on $f$ .

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2020 Computer Science and Information Technology (CS)
Question: 50 of 65, printed as CS Q.40
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source