retagged by
17,821 views
39 votes
39 votes

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,_____________”.

  1. for every $f: V \rightarrow \mathbb{R}$
  2. if and only if $\forall u \in V, \: f(u)$ is positive
  3. if and only if $\forall u \in V, \: f(u)$ is negative
  4. 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$
retagged by

6 Answers

2 votes
2 votes

 

Option A is correct.

 

There is a graph G, let us consider G is this.

Notice in the question there are two functions w, w’ which are assigning weights to the graph.The question already assumes that their shortest paths are same in both w, w’ now they want to find what can be possible.

 

Now if we add some positive number to all the edges to every edge of graph G given here then we may change the shortest path E.g. add 2 to all the edges in G

This is why option B can not be the answer.

 

The same thing will happen if we add some negative number to all the edges then also we will find that shortest paths is changing.

This is why option C can not be the answer.

So we get that we can not add some +ve number also we can not add some -ve number to the previous weights(assigned by w). [Basically , w(u,v) = w’(u,v)]

We have left with one thing only that f(u) - f(v) = 0;

So, f(v) = f(u), for all (u, v) $\epsilon$ E.

This can be satisfied in many ways, E.g. lets take f: V→ R and f(u) = some constant , $\forall$ u $\epsilon$ V. 

So option A is correct

 

 

Now we will talk about option D, here we are adding a new vertex S to G, 

Also f(u) = 0,  u $\epsilon$ V  because  distance(S, u) = 0

Here also  f(v) = f(u), for all (u, v) $\epsilon$ E, is satisfying but this is not the only way.

The condition given is sufficient but not necessary. So “if and only if“ is wrong.



 

0 votes
0 votes
I am writing what I understood from Algorithms by CLRS,

w'(u,v) is a simple transformation of w(u,v)

1) Let G' be the graph with weight function w' on its edges and G be the graph with weight function w on its edges.

2) This transformation is such that the following lemma holds:

(see simple proofs given in book)

lemma 1: The shortest path between any pair of vertices in G will be the same in G'

lemma 2: If G has negative weight cycles then G' also has negative weight cycles and vice versa. (in short "if and only if")

corollary from lemma 2: If G has no negative weight cycles then G' also has no negative weight cycles and vice versa. (in short "if and only if")

So the answer is A) for every f:V -> R
reshown by
Answer:

Related questions

8 votes
8 votes
4 answers
2
Arjun asked Feb 12, 2020
9,630 views
Consider a graph $G = (V,E)$, where $V = \{v_1,v_2, \dots ,v_{100}\}$, $E = \{(v_i,v_j) \mid 1\leq i < j \leq 100\}$, and weight of the edge $(v_i,v_j)$ is $\mid i – j ...