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.

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