Shortest Path

Question 1
Consider a weighted undirected graph with positive edge weights and let uv be an edge in the graph. It is known that the shortest path from the source vertex s to u has weight 53 and the shortest path from s to v has weight 65. Which one of the following statements is always true?
weight (u, v) < 12
weight (u, v) ≤ 12
weight (u, v) > 12
weight (u, v) ≥ 12
       Algorithms        Shortest Path       Gate 2007-IT
Question 1 Explanation: 
Weight (u, v) ≥ 12 (True)
If the weight (u, v) < 12 then
min. weight of (s, v) = weight of (s, u) + weight of (u, v)
= 53 + (<12)
= less than 65
There is 1 question to complete.