Namespaces
Variants
Actions

Difference between revisions of "Dijkstra algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
Line 1: Line 1:
 +
{{TEX|done}}{{MSC|05C85}}
 +
 
''Dijkstra shortest-path algorithm''
 
''Dijkstra shortest-path algorithm''
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d1301001.png" /> be a [[Graph|graph]] with a specified vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d1301002.png" /> and for every edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d1301003.png" /> a non-negative cost (length) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d1301004.png" />. The shortest-path problem is to find a shortest path from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d1301005.png" /> to every other vertex (node) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d1301006.png" />.
+
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|greedy algorithm]]. It proceeds by constructing, one node at a time, a subtree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d1301007.png" /> rooted at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d1301008.png" /> (an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d1301009.png" />-arborescence). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010010.png" /> is connected, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010011.png" /> will be a spanning subtree (at the end).
+
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, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010012.png" />. At any further step one knows the shortest distance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010013.png" /> and corresponding path from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010014.png" /> to any vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010015.png" />. This is the label of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010016.png" />. Of course, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010017.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010018.png" /> for a vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010019.png" /> and a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010020.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010021.png" /> is minimal, and add <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010022.png" /> and the edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010023.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010024.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010025.png" /> spans the connected component of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010026.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010027.png" />. The shortest path from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010028.png" /> to any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010029.png" /> in the connected component of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010030.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010031.png" /> is given by the unique path in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010032.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010033.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010034.png" />; the length is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010035.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010036.png" /> steps, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010037.png" />, the cardinality of the vertex set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010038.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010039.png" />, the cardinality of the set of edges of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130100/d13010040.png" />. It can be done much more efficiently, [[#References|[a3]]].
+
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, [[#References|[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.
 
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====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  "Encyclopedia of Operations Research and Management Science"  S.I. Gass (ed.)  C.M. Harris (ed.) , Kluwer Acad. Publ.  (1996)  pp. 166–167</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  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</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  "Encyclopedia of Operations Research and Management Science"  S.I. Gass (ed.)  C.M. Harris (ed.) , Kluwer Acad. Publ.  (1996)  pp. 166–167</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  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</TD></TR>
 +
</table>

Revision as of 19:40, 6 September 2017

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
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