The GATE Grind

GATE 2025 CS (CS1) – Question 18

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

Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_1(u,v)$ and $d_2(u,v)$ be the shortest distances between $u$ and $v$ in $G$ and $T$, respectively. Which ONE of the options is CORRECT for all possible $G$, $T$, $u$ and $v$?

  1. $d_1(u,v) = d_2(u,v)$
  2. $d_1(u,v) \le d_2(u,v)$
  3. $d_1(u,v) \ge d_2(u,v)$
  4. $d_1(u,v) \ne d_2(u,v)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $d_1(u,v) \le d_2(u,v)$

Explanation

T is a subgraph of G, so every path in T is also a path in G. Hence the shortest distance in G is at most that in T, though the two can differ.