GATE CSE 2025 CS Q37: Algorithms

Let

be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant

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

before and after the edge weight update?

Your answerChoose one option.

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.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

EXPLORE & PRACTISE

Paper and topic context

See where this question comes from and choose what to practise next.

Explore more previous year questions using this question’s imported topic tags.

You’re not logged in. Log in or create an account to see discussions and add comments.