Question

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

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:

Check S1 by comparing the set of paths allowed at k versus k+1, and check S2 by trying to build a small graph with a negative weight edge on the shortest path.

Answer 1

The Correct Option is A

Step 1: Prove S1 is true in general.
By definition, \(d_k(u)\) is the minimum weight over all paths from \(s\) to \(u\) that use at most \(k\) edges, and \(d_{k+1}(u)\) is the minimum weight over all paths that use at most \(k+1\) edges. Every path with at most \(k\) edges is also a path with at most \(k+1\) edges, so the set of candidate paths considered for \(d_{k+1}(u)\) contains every candidate path considered for \(d_k(u)\), plus possibly more. Taking a minimum over a larger set can never produce a larger value than taking the minimum over a subset of it, so\[ d_{k+1}(u) \leq d_k(u) \]for every \(k \geq 0\) and every \(u \in V\), with no dependence on whether the edge weights are positive, negative or zero. This holds even when one or both sides are \(\infty\). So S1 is unconditionally true.
Step 2: Test S2 for a potential counterexample using negative weights.
The problem only states the weights are integers, it does not require them to be non-negative, so a valid counterexample graph is allowed to use negative edge weights (as long as it has no negative weight cycle, so that a shortest path from s to v is well defined). Build a small graph with three vertices \(s, u, v\) and two edges: edge \((s,u)\) with weight 5, and edge \((u,v)\) with weight \(-3\), with \(u\) the only route from \(s\) to \(v\).
Step 3: Compute the relevant distances in this example.
The only path from \(s\) to \(v\) is \(s \to u \to v\), with weight \(5+(-3)=2\), so the shortest path from \(s\) to \(v\) has weight 2 and uses the edge \((u,v)\) as its final edge, exactly the situation S2 talks about. The shortest path from \(s\) to \(u\) has weight 5.
Step 4: Check whether S2's inequality holds here.
For \(k=2\), \(d_2(u)=5\) and \(d_2(v)=2\). S2 claims \(d_k(u) \leq d_k(v)\) should hold, but here \(5 \leq 2\) is false. So S2 fails for this graph, even though \((u,v)\) genuinely lies on the shortest path from \(s\) to \(v\).
Step 5: Explain why this does not contradict any standard shortest path property.
Shortest paths still satisfy \(d(v) = d(u) + w(u,v)\) whenever edge \((u,v)\) lies on a shortest path to \(v\), regardless of the sign of \(w(u,v)\). What S2 additionally assumes, that \(d(u) \leq d(v)\), is only guaranteed when \(w(u,v) \geq 0\); if \(w(u,v)\) is negative, \(d(v)=d(u)+w(u,v)\) is strictly less than \(d(u)\), so the inequality direction in S2 reverses. Since the problem allows integer (including negative) weights, S2 cannot be asserted as universally true.
Step 6: Conclusion.
S1 is always true, and S2 is not always true, so exactly S1 holds in general.\[ \boxed{\text{Only S1 is true (Option A)}} \]