GATE CSE 2025 | Set 2 | Question: 27

Question

​​​​Let $\text{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 $\text{G}$ 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.

Comments

For shortest path take counter example as 1, 1, 3  now suppose 2 is added to all edges then shortest path changes from 2 to 5

---

Caption

---

In the question does it even matter if the edges were negative weighted ?

---

https://gateoverflow.in/511924/go-classes-cs-2026-all-india-mock-test-4-question-19?show=512172#c512172

Answer 1

Option C:

Every MST will remain an MST because if we use Kruskal's Algorithm, adding alpha to each edge weight will not change the ordering of the edges, and the tree will be formed as it is.

for shortest paths, consider an undirected graph of 4  vertices v1, v2, v3, v4. The edge set of this graph is defined as {[v1,v2], [v2,v3], [v3,v4] and [v1,v4]}. Let edge weight of [v1,v2], [v2,v3], [v3,v4] and [v1,v4] be x1, x2, x3 and x4 respectively with the condition: x1+x2+x3 = x4 - 1. Thus originally the shortest path between v1 and v4 is x1+x2+x3. However after adding positive constant to each edge, the shortest path between v1 and v4 is x4 + alpha.

Comments

for $\alpha=1,$ shortest path $AC$ will become $(3+1)\ i.e\ A\to\\C$ instead of $A\to\\B\to\\C$

Answer 2

Let $ G = (V, E) $ be an undirected graph with positive edge weights, and let a positive constant $ \alpha $ be added to the weight of every edge in $ G $. We analyze the effect of this transformation on Minimum Spanning Trees (MSTs) and Shortest Paths (SPs).

Effect on Minimum Spanning Trees

MSTs depend only on the relative ordering of edge weights, not their absolute values. Since adding the same constant $ \alpha > 0 $ to all edges preserves the order of weights, the set of edges selected by Kruskal’s or Prim’s algorithm remains unchanged.

Therefore, every MST of the original graph is also an MST of the modified graph.

Effect on Shortest Paths

Shortest paths, however, depend on the sum of absolute weights along a path. Adding $ \alpha $ to each edge increases the total weight of a path by $ \alpha \cdot (\text{number of edges in the path}) $. Consequently, paths with fewer edges are favored after the transformation even if they were more expensive originally.

Counterexample:
Consider a graph with edges $ AB = 1 $, $ BC = 1 $, and $ AC = 3 $.

• Original shortest path from $ A $ to $ C $: $ A \to B \to C $ (cost = 2).
• After adding $ \alpha = 2 $:
• $ AB = 3 $, $ BC = 3 $, $ AC = 5 $
• Path $ A \to B \to C $ costs 6, while direct edge $ AC $ costs 5.

Shortest path changes.Thus, shortest paths need not remain shortest after the transformation.

• MSTs are invariant under uniform addition of a positive constant to all edge weights.
• Shortest paths are not necessarily preserved.

Hence, the correct statement is:

$$
\color{lime} \boxed{\text{C. Every MST remains an MST, and SPs need not remain SPs.}}
$$

Answer 3

You can see the counter example