CMI2016-A-4

Question

Consider a weighted undirected graph $G$ with positive edge weights. Let $(u, v)$ be an edge in the graph. It is known that the shortest path from a vertex $s$ to $u$ has weight $53$ and the shortest path from $s$ to $v$ has weight $65.$ Which of the statements is always true?

• A. Weight of $(u, v) \leq 12$
• B. Weight of $(u, v) = 12$
• C. Weight of $(u, v) \geq 12$
• D. Nothing can be said about the weight of $(u, v)$

Answer 1

There are two cases
I) let s to v contains u in between (s - u - v)
this means weight of edge (u, v) is 65 - 53 = 12

II) s to v doesn't contain u 
this means edge (u, v) is not choosen for shortest path from s to v
this makes weight of (u, v) > 12

So ans is option C

Answer 2