GATE 2026 CS1 Q.41: solution and answer

GATE 2026 · CS1Q.41 · 2 marks · MCQ

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?

(A)
Only S1 is true
(B)
Only S2 is true
(C)
Both S1 and S2 are true
(D)
Neither S1 nor S2 is true

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct answer is (A) Only S1 is true.

Official answer: ASource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

S1: A path counted for d_k(u) is also a path counted for d_{k+1}(u), so the feasible path set only grows as k increases, and the minimum weight over a larger set can never exceed the minimum over a subset; hence d_{k+1}(u) <= d_k(u) for every k and u, unconditionally. S1 is TRUE.
S2: Build the counterexample graph: vertices s, x, u, v with undirected edges s-x (weight 0), x-u (weight 0), u-v (weight 0), s-v (weight 1).
The true shortest path from s to v is s-x-u-v with weight 0 (versus the direct edge s-v of weight 1), and it uses edge (u,v), so S2's hypothesis holds for this edge.
At k=1: d_1(v)=1 (only the direct edge s-v has length <=1), while d_1(u)=infinity (no edge s-u exists, so u is unreachable within 1 hop).
Checking S2's required inequality: d_1(u) <= d_1(v) becomes infinity <= 1, which is false, so S2 fails despite its hypothesis holding. S2 is FALSE.
Since S1 is always true and S2 is false, the correct choice is Only S1 is true, option A.

KEY IDEA

d_k(u) is monotone non-increasing in k because the set of length-<=k paths is a subset of the length-<=(k+1) paths, so the minimum can only get smaller or stay the same (S1). The claim that d_k(u) <= d_k(v) whenever (u,v) lies on a shortest path to v is false because reaching u may require strictly more hops than reaching v via a different, cheaper route (S2).

WATCH OUT FOR

Assuming S2 must be true by analogy with the Bellman-Ford relaxation step d_{k+1}(v) <= d_k(u) + w(u,v); that inequality involves k and k+1 with an added edge weight, not d_k(u) <= d_k(v) at the same k with no weight term, so the analogy does not transfer and a hop-count counterexample breaks it.

From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

GATE 2026 CS1 Q.41: solution and answer

Answer and solution

More Graph algorithms questions