Dijkstra algorithm

2020 Mathematics Subject Classification: Primary: 05C85 [MSN][ZBL]

Dijkstra shortest-path algorithm

Let $\Gamma=(V(\Gamma),E(\Gamma))$ be a graph with a specified vertex $s$ and for every edge $e \in E(\Gamma)$ a non-negative cost (length) $c(e)$. The shortest-path problem is to find a least cost (shortest) path from $s$ to every other vertex (node) $i$.

Basically, the Dijkstra algorithm, which solves this problem, is a node-labeling greedy algorithm. It proceeds by constructing, one node at a time, a subtree $T$ rooted at $s$ (an $s$-arborescence). If $\Gamma$ is connected, $T$ will be a spanning subtree (at the end).

Initially, $T = \{s\}$. At any further step one knows the shortest distance $d(s,v)$ and corresponding path from $s$ to any vertex $v \in T$. This is the label of $v$. Of course, $d(s,s) = 0$.

Now, look through $V(\Gamma) \setminus V(T)$ for a vertex $v \in V(\Gamma) \setminus V(T)$ and a $u \in V(T)$ for which $d(s,v) + d(vu)$ is minimal, and add $v$ and the edge $vu$ to $T$.

The algorithm stops as soon as $T$ spans the connected component of $s$ in $\Gamma$. The shortest path from $s$ to any $v$ in the connected component of $s$ in $\Gamma$ is given by the unique path in $T$ from $s$ to $v$; the length is $d(s,v)$.

A very rough implementation of Dijkstra's algorithm takes $O(mn)$ steps, where $n$ is, the cardinality of the vertex set $V(\Gamma)$, and $m$ is the cardinality of the set of edge set $E(\Gamma)$. It can be done much more efficiently, [a3].

The algorithm can be easily adapted to directed edge-weighted graphs and networks. As of 2001, there is no efficient algorithm for finding longest paths in loop-free (directed) graphs.

References

[a1]	A. Frank, "Connectivity and network flows" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovász (ed.) , Handbook of Combinatorics , Elsevier (1995) pp. 111–178
[a2]	"Encyclopedia of Operations Research and Management Science" S.I. Gass (ed.) C.M. Harris (ed.) , Kluwer Acad. Publ. (1996) pp. 166–167
[a3]	L. Lovász, D.B. Shmoys, E. Tardos, "Combinatorics in computer science" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovász (ed.) , Handbook of Combinatorics , Elsevier (1995) pp. 2003–2038