Dijkstra

Dijkstra

whatever

Openlearnware

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:

1. 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].
2. 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:

1. [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.
2. For the nodes [math]\displaystyle{ v \in V }[/math] not in [math]\displaystyle{ Q }[/math], it is [math]\displaystyle{ \delta(v) = \Delta(v) }[/math].
3. 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

Abstract view:

1. All nodes of [math]\displaystyle{ V }[/math] except for [math]\displaystyle{ s }[/math] have to be members of [math]\displaystyle{ Q }[/math].
2. Root [math]\displaystyle{ s }[/math] must have correct distance [math]\displaystyle{ \Delta(s) = 0 }[/math].
3. The other nodes must meet Invariant #3.

Implementation:

1. [math]\displaystyle{ \delta(s) := 0 }[/math];
2. For all [math]\displaystyle{ a = (s,v) \in A }[/math], set [math]\displaystyle{ \delta(v) := l(a) }[/math].
3. For all [math]\displaystyle{ v \in V\setminus\{s\} }[/math] with [math]\displaystyle{ (s,v) \notin A }[/math] set [math]\displaystyle{ \delta(v) := +\infty }[/math].
4. Insert all nodes in [math]\displaystyle{ V\setminus\{s\} }[/math] into [math]\displaystyle{ Q }[/math].

Proof:

Obvious.

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