Official PYQ · 2026Set 1 · Q31Graph Traversals (BFS, DFS)MCQ2 marks

GATE CS 2026 Set 1 Q31 — Graph Traversals (BFS, DFS)

Let $G(V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.

Let $s \in V$ be a vertex in $G$ . For every $u \in V$ and for every $k \geq 0$ , let $d_{k}(u)$ denote the weight of a shortest path (in terms of weight) from $s$ to $u$ of length at most $k$ . If there is no path from $s$ to $u$ of length at most $k$ , then $d_{k}(u)=\infty$ .

Consider the statements:

S1: For every $k \geq 0$ and $u \in V, d_{k+1}(u) \leq d_{k}(u)$ .

S2: For every $(u, v) \in E$ , if $(u, v)$ is part of a shortest path (in terms of weight) from $s$ to $v$ , then for every $k \geq 0, d_{k}(u) \leq d_{k}(v)$ .

Which one of the following options is correct?

View worked solution

Answer: A

Statement S1: True

Let $P_k(s, u)$ be the set of all paths from $s$ to $u$ of length at most $k$ . Any path of length at most $k$ is also a path of length at most $k+1$ . Therefore, we have the subset relation:

P_k(s, u) \subseteq P_{k+1}(s, u)

Since $d_k(u)$ is the minimum weight over the set $P_k(s, u)$ , taking the minimum over a larger set $P_{k+1}(s, u)$ cannot increase the minimum weight. Thus, $d_{k+1}(u) \leq d_k(u)$ always holds.

Statement S2: False

We can disprove this statement using a counterexample with positive integer weights. Consider an undirected graph with vertices $\{s, a, u, v\}$ and the following edge weights:

$(s, a) = 2$
$(a, u) = 2$
$(u, v) = 2$
$(s, v) = 7$
$(s, u) = 8$

The shortest path from $s$ to $v$ is $s \to a \to u \to v$ with a total weight of $2 + 2 + 2 = 6$ . The edge $(u, v)$ is part of this shortest path.

Now, let us evaluate $d_k(u)$ and $d_k(v)$ for $k = 1$ :

$d_1(u) = 8$ (via the direct path $s \to u$ of length 1)
$d_1(v) = 7$ (via the direct path $s \to v$ of length 1)

Since $d_1(u) = 8 > d_1(v) = 7$ , the condition $d_k(u) \leq d_k(v)$ is violated for $k = 1$ . Thus, $\text{S2}$ is false.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Graph Traversals (BFS, DFS) questions

GATE CS 2026 Set 1 Q31 — Graph Traversals (BFS, DFS)

Related questions