Namespaces
Variants
Actions

Dijkstra algorithm

From Encyclopedia of Mathematics
Revision as of 16:55, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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
How to Cite This Entry:
Dijkstra algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Dijkstra_algorithm&oldid=41834
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article