The GATE Grind

GATE 2016 CS – Question 24

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Multiple choice

Let $G$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

P: Minimum spanning tree of $G$ does not change

Q: Shortest path between any pair of vertices does not change

  1. P only
  2. Q only
  3. Neither P nor Q
  4. Both P and Q

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) P only

Explanation

Every spanning tree has exactly $|V| - 1$ edges, so adding the same value to every edge raises each spanning tree's weight by the same amount, and the minimum spanning tree stays the same. A path with more edges gains more than a path with fewer edges, so the shortest path between two vertices can change. P is true and Q is false.