Question 3120 – Environment
December 4, 2023GATE 2006
December 4, 2023Question 6276 – Data-Structures
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?
Correct Answer: C
Question 519 Explanation:
If the weight of (u, v) is strictly less than 12, then there is a path from s to v of weight at most 53 + 11 = 64 (which goes from s to u and then takes the edge (u, v)). This contradicts the fact that the shortest path from s to v has weight 65. Thus the weight of (u, v) is at least 12.
Weight of (u, v) ≤ 12.
Weight of (u, v) = 12.
Weight of (u, v) ≥ 12.
Nothing can be said about the weight of (u, v).