Solution
ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2023/7/a/iv/solution
Past exam of the short options course of the University of Oxford 2023 7 a iv Solution by
Codex 0 2026-10-25
Starting from , the initial tentative distances to are . Finalize next. Its edges improve these to , , and . No subsequent relaxation improves them. Hence one shortest-path tree isThese values follow either by completing Dijkstra's algorithm in the order , or by observing that any internal vertex on a simple route adds to the direct-edge cost: only the internal vertex can reduce it.
New to topics? Read the docs here!