Let $G = (V,E)$ be a directed, weighted graph with weight function \(w: E…

PYQ GATE 2020

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)∈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 \rightarrow \mathbb{R}$
B.
if and only if $\forall u \in V, \: f(u)$ is positive
C.
if and only if $\forall u \in 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$

Attempted by 183 students.

Explore the full course: Algorithms

Let \(G = (V,E)\) be a directed, weighted graph with weight function \(w: E…