The GATE Grind

GATE 2015 CS – Question 51

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search (BFS) is performed starting at $s$. Let $T$ be the resultant BFS tree. If $(u, v)$ is an edge of $G$ that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$?

  1. -1
  2. 0
  3. 1
  4. 2

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) 2

Explanation

In an undirected graph, adjacent vertices differ in shortest distance from $s$ by at most 1, because a path to one gives a path to the other with one more edge. So $d(u) - d(v)$ can only be $-1$, $0$ or $1$ for any edge, and a difference of 2 is impossible.