GATE CSE 2026 Session 1 Q41: Shortest paths with at most k edges: two statements

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?