GATE CS 2025 Set 1 Q33 — Shortest Paths (Dijkstra, Bellman-Ford)

The maximum shortest path distance between any two vertices in the graph $G$ is defined as the diameter of the graph. Here, the diameter is:

Let $x, y \in V$ be two vertices such that the shortest path distance between them is exactly $30$, i.e., $d(x, y) = 30$.

Let $T$ be a Breadth-First Search (BFS) tree of $G$ rooted at an arbitrary vertex $r \in V$. The height $h$ of the BFS tree $T$ is the maximum distance from the root $r$ to any other vertex in the graph:

By the triangle inequality of shortest path distances, we have:

Since $d(r, x) \le h$ and $d(r, y) \le h$, we can substitute these into the inequality:

Thus, the height of any BFS tree $T$ must be at least $15$.

Evaluating the Options:

• Option A & B: If we construct $G$ as a simple path of length $30$ (with other vertices connected such that they do not increase the diameter):
  • Choosing the root $r$ at the center of this path yields a BFS tree of height $15$. This disproves Option B.
  • Choosing the root $r$ at one of the endpoints of the path yields a BFS tree of height $30$. This disproves Option A.
• Option D: As shown above, a BFS tree rooted at the center of the path has a height of $15$, which is strictly less than $30$. This disproves Option D.
• Option C: Since $h \ge 15$ holds universally for any choice of root $r$, the height of $T$ is always at least $15$.