Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 7 / d / Solution

Dijkstra's algorithm solves the single-source shortest path problem in a finite weighted graph with nonnegative edge weights. Given a source $s$, it computes for every vertex $v$ the minimum sum of edge weights on a path from $s$ to $v$, reporting $+\infty$ if $v$ is unreachable. Keeping a shortest-path predecessor also recovers the corresponding paths. Directed graphs are allowed; an undirected graph can be represented by two oppositely directed edges. Negative edge weights are outside the algorithm's standard correctness assumptions, while zero weights are allowed.