edited by
2,384 views
12 votes
12 votes

Let $G=(V,E)$ be a DIRECTED graph, where each edge $\large e$ has a positive weight $\large\omega(e),$ and all vertices can be reached from vertex $\large s.$ For each vertex $\large v,$ let $\large \phi(v)$ be the length of the shortest path from $\large s$ to $\large v.$ Let $G'=(V,E)$ be a new weighted graph with the same vertices and edges, but with the edge weight of every edge $\large e=(u\to v)$ changed to $\large \omega'(e)=\omega(e)+\phi(v)-\phi(u).$ Let $P$ be a path from $\large s$ to a vertex $\large v,$ and let $\large \omega(P)=\sum_{e\in P} \omega_{e},$ and $\large \omega'(P)=\sum_{e\in P} \omega'_{e}.$

Which of the following options is NOT NECESSARILY TRUE ?

  1. If $P$ is a shortest path in $G,$ then $P$ is a shortest path in $G'.$
  2. If $P$ is a shortest path in $F',$ then P is a shortest path in $G.$
  3. If $P$ is a shortest path in $G,$ then $\omega'(P)=2\times \omega(P).$
  4. If $P$ is NOT a shortest path in $G,$ then $\omega'(P)<2\times \omega(P).$
  5. All of the above options are necessarily TRUE.
edited by

1 Answer

Best answer
12 votes
12 votes

Answer should be $E,$ i.e., all statements $A,B,C,D$ are correct.

Explanation:

$\omega\left ( P \right ) =\sum_{e} \omega_e$

$\omega'\left ( P \right ) =\sum_{e} \omega_e'$

$\qquad =\sum_{e} (\omega (e) + \phi(v) - \phi(u))$

$\qquad =\sum \omega(e) + \sum ( \phi(v) - \phi(u) )$

Given that $P$ is a path from $s$ to $v.$ Let $P$ be comprised of  $S \rightarrow V_1 \rightarrow V_2 \rightarrow V_3 \cdots \rightarrow V_n \rightarrow V $ 

$\require{cancel} \omega'\left ( P \right ) =\sum_{e} \omega(e) + \phi(v) -\cancel {\phi(v_n)}$

$\qquad  +\cancel {\phi(v_n)} - \cancel{\phi(v_{n-1})}$

$\qquad + $

$\qquad \vdots$

$\qquad  +\cancel {\phi(v_1)} - \phi(v_s) $

$\omega'(P)=\sum \omega(e) +  \phi(v) - \phi(s)$

Since, $s$ is the source (in the context of the shortest path) $\phi (s) = 0.$

$ \therefore \omega'(P) = \sum \omega(e) +  \phi(v) = \omega(P) + \phi(v)$

If $P$ is the shortest path in $G,$ $\omega'(P) = \sum \omega(e) + \phi(v)$ 

$\qquad = \phi(v) + \phi(v)$

$\qquad = 2. \phi(v)$

$\qquad = 2. \sum_{e} \omega_e$

$\qquad =2. \omega(P)$

(C is correct)

$\omega'(P) = \omega(P) + \phi(v)$

$\qquad \le \omega(P) + \omega(P)$

$\qquad  = 2* \omega(P)$

or $\omega'(P) \le 2\omega(P)$                 

(D is correct)

If $P$ is the shortest path in $G,$ (Say from $s$ to $v)$

  • $\omega(P) = \phi(v)$
  • $\omega'(P) = \omega(P) + \phi(v)$

Say $P'$ is the shortest path in $G'$ (not equal to $P)$

$\omega'(P') \le \omega'(P)$

$\Rightarrow \omega(P') + \phi(v) \le \omega(P) + \phi(v)$

$\Rightarrow \omega(P') \le \omega(P) \Rightarrow$ Contradiction as we assumed $P$ to be shortest path in $G$

$\therefore$ $P$ is the shortest path in $G'$ as well.               

(A is correct)

Similarly say $P$ is the shortest path in $G'$ $(s$ to $v)$

$\omega'(P) = \omega(P) + \phi(v)$

We claim $P$ is the shortest path in $G$ as well. By contradiction let us assume $P'$ is the shortest path in $G.$

$\omega(P') \le \omega(P)$

$\omega(P') + \phi(v) \le \omega(P) + \phi(v)$

$\omega'(P') \le \omega'(P) \Rightarrow$ Contradiction

Here, what we assumed was wrong and $P$ is the shortest path in $G$     

(B is correct)

$\therefore$ E is the answer

edited by
Answer:

Related questions

13 votes
13 votes
1 answer
2
9 votes
9 votes
2 answers
4
Arjun asked Dec 10, 2017
2,569 views
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?$1$$2$$4$$6$$8$