Dijkstra algorithm

Dijkstra shortest-path algorithm

Let be a graph with a specified vertex and for every edge a non-negative cost (length) . The shortest-path problem is to find a shortest path from to every other vertex (node) .

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 rooted at (an -arborescence). If is connected, will be a spanning subtree (at the end).

Initially, . At any further step one knows the shortest distance and corresponding path from to any vertex . This is the label of . Of course, .

Now, look through for a vertex and a for which is minimal, and add and the edge to .

The algorithm stops as soon as spans the connected component of in . The shortest path from to any in the connected component of in is given by the unique path in from to ; the length is .

A very rough implementation of Dijkstra's algorithm takes steps, where , the cardinality of the vertex set of , and , the cardinality of the set of edges of . 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