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

A different way to reach the same conclusion is to analyse S1 and S2 purely through the recursive relaxation formula that $d_k$ satisfies, instead of arguing about feasible path sets and a specific numeric counterexample.

Step 1: Write the standard recurrence for $d_k$.
By definition, a shortest path to $u$ using at most $k$ edges either uses at most $k-1$ edges already, or it uses exactly $k$ edges, meaning its last edge is some $(w,u) \in E$ and the first $k-1$ edges form a shortest path of at most $k-1$ edges to $w$. This gives the recurrence, valid for any integer edge weights so long as no negative cycle is reachable:$$ d_k(u) = \min\Big( d_{k-1}(u),\ \min_{(w,u)\in E} \big[ d_{k-1}(w) + \text{weight}(w,u) \big] \Big) $$Step 2: Re derive S1 from this recurrence.
The recurrence for $d_k(u)$ explicitly includes the term $d_{k-1}(u)$ inside a minimum, so by definition of minimum,$$ d_k(u) \leq d_{k-1}(u) $$Re-indexing $k \to k+1$ gives $d_{k+1}(u) \leq d_k(u)$ for every $k \geq 0$, exactly S1, and this falls directly out of the recurrence with no assumption on edge weight signs, confirming S1 is always true.
Step 3: Re examine S2 using the recurrence.
Suppose $(u,v) \in E$ lies on a shortest path to $v$, so for suitably large $k$, the recurrence's minimisation over incoming edges to $v$ is realised by the term coming from $u$:$$ d_k(v) = d_{k-1}(u) + \text{weight}(u,v) $$If $\text{weight}(u,v) \geq 0$, then $d_k(v) \geq d_{k-1}(u) \geq d_k(u)$, which would support S2. But if $\text{weight}(u,v) < 0$, the equation gives $d_k(v) < d_{k-1}(u)$, and no valid derivation of $d_k(u) \leq d_k(v)$ exists from this recurrence once the edge weight is negative.
Step 4: Confirm with the same small example as an existence check.
Since the recurrence only shows S2 is unsupported once negative weights are allowed, one legal graph is enough to disprove it: $s\to u$ weight 5, $u \to v$ weight $-3$, which gives $d(u)=5>2=d(v)$, directly contradicting S2.

Step 5: Conclusion.
The recurrence proves S1 unconditionally and shows S2 has no valid unconditional derivation once negative weights are permitted, consistent with the explicit counterexample, so only S1 is true.$$ \boxed{\text{Only S1 is true (Option A)}} $$