GATE 2026 CS (CS1) – Question 41
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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) Only S1 is true
Explanation
- **Statement S1**: $d_k(u)$ is defined as the minimum weight over 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$. Minimizing over a larger set of valid paths can only decrease or preserve the minimum weight. Hence, $d_{k+1}(u) \le d_k(u)$ for all $k \ge 0$. S1 is TRUE.
- **Statement S2**: Suppose $(u, v)$ is part of a global shortest path from $s$ to $v$ where $u$ is at distance 2 edges from $s$ while $v$ has a direct edge from $s$ of larger weight. For $k = 1$, $d_1(u) = \infty$ while $d_1(v) < \infty$. Thus $d_1(u) > d_1(v)$, which violates $d_k(u) \le d_k(v)$ for all $k$. Hence S2 is FALSE.
Therefore, only S1 is true. Option (A) is correct.