Question

Let 𝐺(𝑉, 𝐸) 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 𝑠∈𝑉 be a vertex in 𝐺. For every 𝑢∈𝑉 and for every 𝑘 ≥0, let 𝑑𝑘(𝑢) denote
the weight of a shortest path (in terms of weight) from 𝑠 to 𝑢 of length at most 𝑘. If
there is no path from 𝑠 to 𝑢 of length at most 𝑘, then 𝑑𝑘(𝑢) = ∞.
Consider the statements:
S1:
For every 𝑘 ≥0 and 𝑢 ∈𝑉, 𝑑𝑘+1(𝑢) ≤𝑑𝑘(𝑢).
S2:
For every (𝑢, 𝑣) ∈𝐸, if (𝑢, 𝑣) is part of a shortest path (in terms of
weight) from 𝑠 to 𝑣, then for every 𝑘≥ 0, 𝑑𝑘(𝑢) ≤𝑑𝑘(𝑣).
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

Hint:

Compare the set of length-at-most-k paths to length-at-most-(k+1) paths for S1 (superset argument), and try building a graph where the predecessor u on the shortest weighted path to v needs more edges to reach than a direct shortcut to v needs, to test S2.

Answer 1

The Correct Option is A

Step 1: Understand the definitions. For every \(k \ge 0\), \(d_k(u)\) is the smallest total weight among all paths from \(s\) to \(u\) that use at most \(k\) edges. If no such short path exists, \(d_k(u) = \infty\).

Step 2: Check statement S1. The collection of paths from \(s\) to \(u\) with length at most \(k+1\) contains every path with length at most \(k\) (a path with \(\le k\) edges automatically has \(\le k+1\) edges). Since \(d_{k+1}(u)\) is a minimum taken over a bigger (or equal) set of candidate paths than \(d_k(u)\), we get \[ d_{k+1}(u) \le d_k(u) \quad \text{for every } k \ge 0, u \in V. \] So S1 is always true, independent of the graph or the edge weights.

Step 3: Test statement S2 with a counterexample. S2 claims that if edge \((u,v)\) lies on the overall shortest \(s\)-to-\(v\) path, then \(d_k(u) \le d_k(v)\) for every \(k\). Build a small graph:

• \(s-y\) weight 1, \(y-u\) weight 1 (u is reachable from s only through y, needing 2 edges), and \(u-v\) weight 0.
• \(s-v\) direct edge, weight 5.

The path \(s \to y \to u \to v\) has weight \(1+1+0=2\), which is less than the direct edge weight 5, so this is the overall shortest path to \(v\), and edge \((u,v)\) lies on it - the hypothesis of S2 is satisfied.

Step 4: Compute \(d_1(u)\) and \(d_1(v)\). To reach \(u\) with at most 1 edge there is no route at all (the only path to \(u\) needs 2 edges), so \(d_1(u) = \infty\). To reach \(v\) with at most 1 edge, use the direct edge \(s-v\), giving \(d_1(v) = 5\), a finite number.

Here \(d_1(u) = \infty\) is NOT \(\le d_1(v) = 5\). This directly contradicts S2, so S2 is false in general.

Step 5: Conclusion. S1 always holds, S2 can fail, so only S1 is true.

\[\boxed{\text{Only S1 is true} \Rightarrow \text{Option A}}\]