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

Every spanning tree has exactly $n-1$ edges, so all tree weights shift by the same amount and MSTs are preserved. Paths have different numbers of edges, so a path with more edges gets penalized more and shortest paths can change.