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 / e

Use an indexed priority queue of unsettled vertices, keyed by their tentative distances. Initialize the source to zero and other keys to $+\infty$. Each ExtractMin settles the currently closest vertex. Scan its outgoing edges; whenever edge relaxation improves a neighbour's tentative distance, update that neighbour with DecreaseKey. Already settled vertices need no further update, by the correctness of Dijkstra's algorithm for nonnegative weights.

There are at most $|V|$ extractions and at most $|E|$ successful decreases. The indexed priority queue maintains each vertex's current array position and updates this index table on every swap, so locating a key for DecreaseKey costs $O(1)$. Preallocate capacity $|V|$. Repeated insertion costs $O(|V|(1+{\log }_d|V|))$, or bottom-up heap construction initializes the queue in $O(|V|)$ time. Scanning adjacency lists costs $O(|V|+|E|)$ in total.

For $|V|\ge 2$ and $2\le d\le |V|$, the heap-operation contributions are thereforeand the overall bound isA uniform bound including larger arity and tiny graphs is $O((d|V|+|E|)(1+{\log }_d(\max (2,|V|))))$. Arity greater than the number of vertices offers no useful extra heap levels. These bounds assume adjacency lists; with an adjacency matrix, scanning neighbours contributes $O(|V{|}^2)$ instead. No rebuilding of the heap is required after each decrease.