Consider a weighted directed graph. The current shortest distance from source…
2019
Consider a weighted directed graph. The current shortest distance from source 𝑆 to node 𝑥 is represented by 𝑑[𝑥]. Let 𝑑[𝑣]=29, 𝑑[𝑢]=15, 𝑤[𝑢,𝑣]=12. What is the updated value of 𝑑[𝑣] based on current information?
- A.
29
- B.
27
- C.
25
- D.
17
Attempted by 196 students.
Show answer & explanation
Correct answer: B
Key idea: apply the relaxation rule d[v] = min(d[v], d[u] + w[u,v]).
Compute the path length through u: d[u] + w[u,v] = 15 + 12 = 27.
Compare with the current value d[v] = 29 and take the minimum: min(29, 27) = 27.
Update d[v] to 27.
Updated value: d[v] = 27.
A video solution is available for this question — log in and enroll to watch it.