Dijkstra
Dijstra's algorithm is a graph algortihm solving the single-source shortest-paths problem.
Requirements
- directed Graph [math]\displaystyle{ G=(V,E) }[/math]
- weight function [math]\displaystyle{ w\colon E\to\mathbb R }[/math]
- [math]\displaystyle{ \forall(u,v)\in E\colon w(u,v)\geq 0 }[/math]
- source [math]\displaystyle{ s\in V }[/math]
- Datastruct [math]\displaystyle{ S }[/math]
- Datastruct [math]\displaystyle{ Q }[/math]
General information
Algorithmic problem: Single source shortest paths
Prerequisities: For all [math]\displaystyle{ \alpha \in A }[/math], it is [math]\displaystyle{ l(a) \geq 0 }[/math].
Type of algortihm: loop
Auxiliary data:
- A temporary distance value [math]\displaystyle{ \delta(v) \in \R }[/math] for each node [math]\displaystyle{ v \in V }[/math]. At termination, it is [math]\displaystyle{ \delta(v) = \Delta(v) }[/math] for all [math]\displaystyle{ v \in V }[/math].
- A bounded priority queue [math]\displaystyle{ Q }[/math] of size [math]\displaystyle{ |V|-1 }[/math], which contains nodes from [math]\displaystyle{ V }[/math] and takes their [math]\displaystyle{ \delta }[/math]-values as keys. The node with minimal key is returned.
Abstract view
Invariant: After [math]\displaystyle{ i \geq 0 }[/math] iterations:
- [math]\displaystyle{ Q }[/math] contains all nodes of [math]\displaystyle{ V }[/math] except for [math]\displaystyle{ s }[/math] and [math]\displaystyle{ i }[/math] further nodes.
- For the nodes [math]\displaystyle{ v \in V }[/math] not in [math]\displaystyle{ Q }[/math], it is [math]\displaystyle{ \delta(v) = \Delta(v) }[/math].
- For the nodes [math]\displaystyle{ v \in V }[/math] in [math]\displaystyle{ Q }[/math], [math]\displaystyle{ \delta(v) }[/math] is the length of a shortes [math]\displaystyle{ (s,v) }[/math]-path that solely contains nodes not in [math]\displaystyle{ Q }[/math] (except for [math]\displaystyle{ v }[/math] itself, of course). As usual, this means [math]\displaystyle{ \delta(v) = +\infty }[/math] if there is no such path.
In particular, it is [math]\displaystyle{ \delta(v) \geq \Delta(v) }[/math] for each node [math]\displaystyle{ v \in V }[/math].
Variant: [math]\displaystyle{ i }[/math] increases by [math]\displaystyle{ 1 }[/math].
Break condition:
- [math]\displaystyle{ Q = \empty }[/math], which means that all nodes are reachable from [math]\displaystyle{ s }[/math] and have been processed;
- otherwise, if [math]\displaystyle{ \delta(v) = +\infty }[/math] for the noext node [math]\displaystyle{ v }[/math] of [math]\displaystyle{ Q }[/math], which means that [math]\displaystyle{ \delta(v) = + \infty }[/math] for every node in [math]\displaystyle{ Q }[/math] and hence none of the nodes in [math]\displaystyle{ Q }[/math] is reachable from [math]\displaystyle{ s }[/math].
Induction basis
Induction step
Complexity
Pseudocode
DIJKSTRA(G,w,s)
DIJKSTRA(G,w,s)
1 INITIALIZE-SINGLE-SOURCE(G,s)
2 S = ∅
3 Q = G.V
4 while Q ≠ ∅
5 u = EXTRACT-MIN(Q)
6 S = S ∪ {u}
7 for each vertex v ∈ G.Adj[u]
8 RELAX(u,v,w)
RELAX(u,v,w)
RELAX(u,v,w)
1 if v.d > u.d + w(u,v)
2 v.d = u.d + w(u,v)
3 v.π = u
INITIALIZE-SINGLE-SOURCE(G,s)
INITIALIZE-SINGLE-SOURCE(G,s)
1 for each vertex v ∈ G.V
2 v.d = ∞
3 v.π = NIL
4 s.d = 0