GATE CS 2025 (Afternoon) — Question 37

AlgorithmsMinimum Spanning Trees (Prim/Kruskal Algorithms)MCQ2 marks · −2/3 if wrongMedium

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. A
    Every MST remains an MST, and every SP remains an SP.
  2. B
    MSTs need not remain MSTs, and every SP remains an SP.
  3. C
    Every MST remains an MST, and SPs need not remain SPs.
  4. D
    MSTs need not remain MSTs, and SPs need not remain SPs.
Practise the full 2025-AN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Minimum Spanning Trees (Prim/Kruskal Algorithms)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group