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

Correct Answer is : If and only if ∀u∈V,f(u) is positive

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

If and only if \forall {u} \in V, {f}( {u}) is positive

If and only if \forall {u} \in V, {f}( {u}) is negative

GATE Computer Science (CS) 2020 Solved Papers

Question : 65 of 65

Marks: +1, -0

Let

G=(V, E)

be a directed, weighted graph with weight function

{w}: {E} → {R}

. For some function

f : V \to R .

for each edge

(u, v) ∈ E_{t}

define

w'(u, 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

G

under

w

are shortest paths under

{w}^{'}

too, _____.

if and only if f(u) is the distance from s to u in the graph obtained by adding new vertexs to G and edges of zero weight from s to every vertex of G.
for every $f : V \to R$
If and only if $∀ {u} ∈ V, {f}( {u})$ is positive
If and only if $∀ {u} ∈ V, {f}( {u})$ is negative

Validate

Go to Question:

Prev Question