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 65 students.
Show answer & explanation
Correct answer: C
In a weighted graph, the shortest path distance satisfies the triangle inequality. For edge (u, v), dist(s, v) ≤ dist(s, u) + weight(u, v). Substituting the given values: 65 ≤ 53 + w. Therefore, the edge weight must be at least 12.
A video solution is available for this question — log in and enroll to watch it.