Let s ∈ V be a vertex in G. For every u ∈ V and for every k ≥ 0, let dk(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 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 (in terms of weight) from s to v, then for every k ≥ 0, dk(u) ≤ dk(v).
Which one of the following options is correct?
Correct : a
dk(u) is the minimum weight path from s to u using at most k edges. The graph has integer weights which may be negative.
S1 — True
dk+1(u) allows paths of at most k+1 edges, which is a strictly larger set than paths of at most k edges. Any path that achieves dk(u) is also a valid candidate for dk+1(u) since it uses at most k edges which is ≤ k+1. So dk+1(u) can only be equal to or smaller than dk(u) — the minimum over a larger set cannot be larger than the minimum over a smaller set. With negative weights, taking an extra edge might even reduce the path weight further, which still satisfies the ≤ direction. S1 always holds.
S2 — False
S2 claims that if (u, v) is on the shortest path to v then dk(u) ≤ dk(v) for every k. This fails when negative weights are present. Consider: s→v has weight 2 (direct, 1 edge). s→u→v has weights 5 and −10 respectively, giving total weight −5, which is the shortest path to v. So (u,v) is part of the shortest path to v. But d1(u) = 5 (one edge s→u) while d1(v) = 2 (one edge s→v directly), so d1(u) = 5 > 2 = d1(v), violating S2. The problem is that reaching u may require more edges than reaching v directly, so the k-constrained distances can go either way. S2 is false.
Correct answer: A — Only S1 is true ✓
Similar Questions
Total Unique Visitors