Let 𝐺 be an edge-weighted undirected graph with positive edge weights.…
GATE · 2025 · CS · Set 2 · Computer Science & IT
Let 𝐺 be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant 𝛼 is added to the weight of every edge.
Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in 𝐺 before and after the edge weight update?
- A.
Every MST remains an MST, and every SP remains an SP.
- B.
MSTs need not remain MSTs, and every SP remains an SP.
- C.
Every MST remains an MST, and SPs need not remain SPs.
- D.
MSTs need not remain MSTs, and SPs need not remain SPs.
Attempted by 281 students.
Show answer
Correct answer: C
The worked solution is available to enrolled students.
Video solution available to enrolled students.
Explore the full course: Iocl Engineers Officers Grade A Paper 2