Let G(V, E) be an undirected, edge-weighted graph with integer weights. The…

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

Let s ∈ V be a fixed source vertex. For u ∈ V and each non-negative integer k, let dk(u) denote the minimum weight of a path from s to u that uses at most k edges. Thus, k is the maximum number of edges allowed, not an edge weight. If no such path exists, then dk(u) = ∞.

Consider the statements:

• S1: For every k ≥ 0 and u ∈ V, dk+1(u) ≤ dk(u).

• S2: For every (u, v) ∈ E, if (u, v) is part of a shortest path from s to v, then for every k ≥ 0, dk(u) ≤ dk(v).

Which one of the following options is correct?