= Solution
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|\geq2$ and $2\leq d\leq|V|$, the heap-operation contributions are therefore
$$
O(|V|d\log_d|V|)\quad\text{and}\quad O(|E|\log_d|V|),
$$
and the overall bound is
$$
\boxed{O\!\left((d|V|+|E|)\log_d|V|\right)}.
$$
A 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.
Back to article page
