Let πΊ(π,πΈ) be an undirected, edge-weighted graph with integer weights. Theβ¦
2026
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 Sβπ 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
Attempted by 19 students.
Show answer & explanation
Correct answer: A
Given:
d_k(u) denotes the shortest path weight from s to u
using at most k edges.
--------------------------------------------------
Statement S1
--------------------------------------------------
d_(k+1)(u) <= d_k(u)
Reason:
All paths allowed for d_k(u)
are also allowed for d_(k+1)(u).
Allowing one extra edge can only improve
or maintain the shortest path value.
Therefore:
S1 is TRUE.
--------------------------------------------------
Statement S2
--------------------------------------------------
Claim:
d_k(u) <= d_k(v)
This is FALSE.
Counterexample:
s -> u = 5
u -> v = -10
Then:
d(u) = 5
d(v) = -5
Thus:
d(u) > d(v)
Hence the statement does not always hold.
Therefore:
S2 is FALSE.
--------------------------------------------------
Final Answer
--------------------------------------------------
Only S1 is true.
"""