Skip to content
GATEiit

GATE CSE 2025 Session 2 Q37: MSTs and shortest paths after adding α to every edge

Question

Let GG 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 GG before and after the edge weight update?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2025 final answer key)

Concept used: Every spanning tree has ∣V∣−1|V| - 1 edges, but paths can have different numbers of edges.

First step: Each spanning tree's weight rises by exactly (∣V∣−1)α(|V|-1)\alpha; a path with kk edges rises by kαk\alpha, which penalises long paths.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 2 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2025 Session 2 questions →