GATE Overflow Test Series | Algorithms | Test 2 | Question: 29

Question

Consider a weighted undirected graph with distinct positive edge weights and let $(u,v)$ be an edge in the graph. It is known that the shortest path from the source vertex $s$ to $u$ has weight $36$ and the shortest path from $s$ to $v$ has weight $44$. Which of the following statements is/are always TRUE? (Mark all the correct options)

• A. weight $(u, v) < 8$
• B. weight $(u, v) \leq 8$
• C. weight $(u, v) > 8$
• D. weight $(u, v) \geq 8$

Comments

This is from Trinagle Inequality problem(Lemma 24.10 Clrs page 650)

For any edge (u,v)  we have d(s,v)<= d(s,u) + w(u,v)

d(s,v)=shortest path from source vertex s to v

---

always word is very beautiful.

---

ALWAYS create trap ALWAYS . Beaware ALWAYS :(

Answer 1

The difference between the shortest distances to $u$ and $v$ is $44-36 = 8.$ So, if the weight of $(u,v)$ is less than $8,$ the difference in shortest distances becomes less than $8$ which is not possible. So options A and B are not possible.
    
    If weight $(u,v) = 8,$ all conditions are satisfied and option C is not satisfying.
    
    So, correct answer is option D.

Comments

Option C is useless option

Only Option D is correct

Even I marked option C and D

---

@shashank i am not able to get it, how option c is useless and if it is useless why it is even given in options, please clarify

---

In the question, ALWAYS is the key. If asked “which of these is/are true”, then C and D are correct. But C won’t be true ALWAYS.