 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2023/functional-programming-design-and-analysis-of-algorithms/5/a/ii/solution

Use source

1

, as in the preceding part. The Dijkstra algorithm extracts vertices in the order $1, 3, 4, 2$ . Distances after relaxing the outgoing edges of each extracted vertex are

extracted vertex initial 1342 d [1] 00000 d [2] \infty 6544 d [3] \infty 2222 d [4] \infty \infty 333

2

1 \to 3 \to 4 \to 2

2 + 1 + 1 = 4

; the direct route to

2

and the route via

3 \to 2

are both heavier.

 New to topics? Read the docs here!