The GATE Grind

GATE 2025 CS (CS2) – Question 37

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

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?

  1. Every MST remains an MST, and every SP remains an SP.
  2. MSTs need not remain MSTs, and every SP remains an SP.
  3. Every MST remains an MST, and SPs need not remain SPs.
  4. MSTs need not remain MSTs, and SPs need not remain SPs.

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

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →