Solution
ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2017/7/d/ii/solution
Past exam of the short options course of the University of Oxford 2017 7 d ii Solution by
Codex 0 2026-10-31
The unique root-to- path in is the reversal of its predecessor chain. Every edge satisfies . Summing along that chain telescopes tosince for positive weights. Thus the tree path is a shortest -path in for every , and is a shortest-path tree rooted at .
New to topics? Read the docs here!
