Best-First: Dijkstra’s Algorithm

Proof of tenseness property in Dijkstra’s algorithm

If we replace the FIFO queue in breadth-first search with a priority queue, where the key of a vertex $v$ is its tentative distance $dist(v)$, we obtain an algorithm first published in 1957 by a team of researchers at the Case Institute of Technology led by Michael Leyzorek in an annual project report for the Combat Development Department of the US Army Electronic Proving Ground. The same algorithm was independently discovered by Edsger Dijkstra in 1956 (but not published until 1959), again by George Minty sometime before 1960, and again by Peter Whiting and John Hillier in 1960. A nearly identical algorithm was also described by George Dantzig in 1958. Although several early sources called it “Minty’s algorithm,” this approach is now universally known as “Dijkstra’s algorithm,” in full accordance with Stigler’s Law. The pseudocode for this algorithm is shown below.

An easy induction proof implies that at all times during the execution of this algorithm, an edge $u\rightarrow v$ is tense if and only if vertex $u$ is either in the priority queue or is the vertex most recently extracted from the priority queue. Thus, Dijkstra’s algorithm is an instance of Ford’s general strategy, which implies that it correctly computes shortest paths, provided there are no negative cycles in $G$.

In the image below, we compute shortest paths in a dag by relaxing outgoing edges in topological order. In each iteration, bold edges indicate predecessors, and the bold vertex is about to be scanned.

$\underline{Dijkstra(s):} \\ \hspace{0.4cm} InitSSSP(s) \\ \hspace{0.4cm} Insert(s, 0) \\ \hspace{0.4cm} while\space the\space priority\space queue\space is\space not\space empty \\ \hspace{1cm} u ← ExtractMin( ) \\ \hspace{1cm} for\space all\space edges\space u\rightarrow v \\ \hspace{1.7cm} if \space u\rightarrow v\space is\space tense \\ \hspace{2.3cm} Relax(u\rightarrow v) \\ \hspace{2.3cm} if\space v\space is\space in\space the\space priority\space queue \\ \hspace{2.7cm} DecreaseKey(v, dist(v)) \\ \hspace{2.3cm} else \\ \hspace{2.7cm} Insert(v, dist(v))$ ...