Consider a weighted undirected graph with positive edge weights and let (u, v)…
2012
Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex s to u has weight 53 and shortest path from s to v has weight 65. Which statement is always true?
- A.
Weight (u, v) < 12
- B.
Weight (u, v) = 12
- C.
Weight (u, v) > 12
- D.
Weight (u, v) ≥ 12
Attempted by 47 students.
Show answer & explanation
Correct answer: D
In a weighted undirected graph, shortest path distances satisfy the triangle inequality. Since the shortest path to v is 65 and via u it would be at least 53 plus the edge weight, we have 65 ≤ 53 + w(u,v). Rearranging gives w(u,v) ≥ 12.
A video solution is available for this question — log in and enroll to watch it.