Let 𝐺 be an edge-weighted undirected graph with positive edge weights.…
PYQ GATE 2025
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 360 students.
Sign up free to check your answer
Sign up freeLoading lesson…