Q40

MCQ2 marks, −0.67

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}'(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$

Loading…