GATE CS 2026 Set 1 Q.41: Single-Source and All-Pairs Shortest Paths

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 \ge 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 \ge 0$ and $u \in V$ , $d_{k+1}(u) \le 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 \ge 0$ , $d_k(u) \le d_k(v)$ .

Which one of the following options is correct?

Only S1 is true

Only S2 is true

Both S1 and S2 are true

Neither S1 nor S2 is true

Official answer and solution

Official answer: A
From: Official GATE 2026 answer key

Solution

Check monotonicity of $d_k(u)$ in $k$ (S1) and test S2 when a shorter-hop path to $v$ exists or when edge weights are negative.

S1 is true: Let $\mathcal{P}_k(u)$ be the set of paths from $s$ to $u$ of length at most $k$ . Since $\mathcal{P}_k(u) \subseteq \mathcal{P}_{k+1}(u)$ , taking the minimum path weight over a larger set of allowed paths can only decrease or keep the minimum unchanged: $d_{k+1}(u) \le d_k(u)$ .
S2 is false: Consider a graph with vertices $\{s, a, u, v\}$ and edges $(s, a)$ of weight $1$ , $(a, u)$ of weight $1$ , $(u, v)$ of weight $1$ , and a direct edge $(s, v)$ of weight $10$ . The unique shortest path from $s$ to $v$ in terms of weight is $s - a - u - v$ (weight $3$ , length $3$ ), which contains $(u, v)$ . However, for $k = 1$ , there is a 1-edge path from $s$ to $v$ of weight $10$ ( $d_1(v) = 10$ ), whereas there is no path from $s$ to $u$ of length at most $1$ ( $d_1(u) = \infty > d_1(v)$ ). (Moreover, if $(u, v)$ has a negative integer weight, $d_k(v)$ can also be strictly less than $d_k(u)$ .)

Final answer

Option (A)

Common trap

Assuming $d_k(u) \le d_k(v)$ holds for every $k$ just because $d(u) \le d(v)$ holds for unconstrained non-negative shortest paths.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 41 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source