Does adding a constant to all edge weights change the Minimum Spanning Tree?

No. Adding a constant value to every edge weight does not change the MST. The relative ordering of edge weights remains the same, so the same set of edges that formed the MST before will still form the MST after the update. Algorithms like Kruskal's and Prim's depend only on comparing edge weights, not their absolute values.

Does adding a constant to all edge weights change the Shortest Path?

Yes, it can change the shortest path. Unlike MST, the shortest path between two vertices depends on the number of edges in the path. A path with fewer edges gets a smaller total addition than a path with more edges. So the relative total costs of different paths can change, and the shortest path may shift to a different route.

What is the correct answer for GATE 2025 CS Set 2 Question 37?

The correct answer is Option C: Every MST remains an MST, and shortest paths need not remain shortest paths.

Why does MST stay the same when a constant is added to all edge weights?

MST algorithms select edges based on their relative weights — they always pick the minimum weight edge that does not form a cycle (Kruskal's) or the minimum weight edge connecting the growing tree to a new vertex (Prim's). Adding a constant to all edges shifts every edge's weight by the same amount, so the relative ordering remains identical. The same edges are still chosen.

Can you give an example where shortest path changes after adding a constant to edge weights?

Yes. Consider vertices A, B, C with edges A-B=1, B-C=1, and A-C=3. Shortest path A to C is via B with cost 2. Now add 3 to all edges: A-B=4, B-C=4, A-C=6. Now A-B-C costs 8 but direct A-C costs 6. The shortest path changed from A→B→C to A→C directly.

GATE 2025 CS Set 2 Q37: MST & Shortest Path After Adding Constant to Edge Weights

Computer Sciences > GATE 2025 SET-2 > Graph Algorithms

Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant a 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?

Every MST remains an MST, and every SP remains an SP.

MSTs need not remain MSTs, and every SP remains an SP.

Every MST remains an MST, and SPs need not remain SPs.

MSTs need not remain MSTs, and SPs need not remain SPs.

Correct : c

The correct answer is Option C - Every MST remains an MST, but shortest paths need not remain shortest paths.
MST - stays the same:
MST algorithms like Kruskal's and Prim's work on relative edge weights. Adding a constant a to every edge shifts all weights equally, so the ordering of edges doesn't change. The same edges get picked — MST is preserved.
Shortest Path — can change:
A path with k edges gets its total cost increased by k × a. So paths with fewer hops get a smaller penalty than paths with more hops. This imbalance can flip which path is shortest.
Quick example — A→B = 1, B→C = 1, A→C = 3. Shortest path A to C is via B (cost 2). Add a = 3 to all edges: A→B = 4, B→C = 4, A→C = 6. Now A→B→C costs 8, but direct A→C costs 6. The shortest path changed.
MST survives uniform weight addition. Shortest paths don't always.

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev