GATE 2025 CS (CS2) – Question 37
Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ 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 $G$ before and after the edge weight update?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) Every MST remains an MST, and SPs need not remain SPs.
Explanation
A spanning tree always has exactly $n-1$ edges, whatever the weights are.
**MST.** Adding $\alpha$ to every edge adds exactly $(n-1)\alpha$ to the weight of every spanning tree. All trees shift by the same amount, so the cheapest tree is still the cheapest. **Every MST stays an MST.**
**Shortest paths.** A path with $k$ edges gets heavier by $k\alpha$. A path with more edges is penalised more. Example: path A with 1 edge of weight 10 versus path B with 3 edges of weights 3, 3, 3 (total 9). B is shorter. Adding $\alpha=2$ gives A $=12$, B $=15$, so A becomes shorter. **Shortest paths can change.**
Answer: option (C).
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2025 CS (CS2) Q59
- GATE 2024 CS (CS1) Q45
- GATE 2024 CS (CS1) Q60
- GATE 2024 CS (CS2) Q59
- GATE 2023 CS Q56
- GATE 2022 CS Q49
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →