Solution

ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2017/7/d/ii/solution

The unique root-to- path in is the reversal of its predecessor chain. Every edge satisfies . Summing along that chain telescopes to
since for positive weights. Thus the tree path is a shortest -path in for every , and is a shortest-path tree rooted at .
Figure 1.
Negative weights obstruct a shortest-path tree; positive predecessors decrease distance
. Original examples. In the left triangle, the two individually shortest root paths require all three edges. In the right graph, selected predecessors point strictly toward smaller root distances and therefore form a tree. Details.

New to topics? Read the docs here!