Dijkstra - Algorithmus

Der Algorithmus Shortest Path First wurde von Edsger Wybe Dijkstra entwickelt und wird unteranderem in der Netzwerktechnik verwendet, um den kürzesten Pfad zwischen zwei Knoten in einem Netzwerk zu ermitteln.

In dem Algorithmus werden alle Knoten in zwei Kategorien unterteilt:

1. Gruppe der beurteilten Knoten (E)
2. Gruppe der restlichen Knoten (R)
3. Geordnete Liste der Pfade (O) anhand ihrer Metrik (steigend)

Für die beurteilten Knoten ist der kürzeste Pfad bekannt.

1. Initialsierung der einzelnen Gruppen, E enthält nur den Quellknoten S und R alle anderen Knoten. Die Liste O wird nur mit dem Ein-Segment-Pfad initialisiert, welcher bei S beginnt. Die Kosten der Pfade entspricht der Metrik der Verbindung
2. Wenn die Liste O leer ist , oder der erste Pfad die Metrik unendlich hat werden alle übringen Knoten in R als nicht erreichbar markiert und der Algorithmus ist beendet.
3. Entnehme den kürzesten Pfad P aus O (1.Element), Entnehme den längsten Pfad V aus O (das letzte Element), wenn V schon in E enthalten ist mache mit Schritt 4 weiter. Sonst ist P der kürzeste Pfad zu V, daher verschiebe V von R nach E und mache bei Schritt 5 weiter.
4. Nimm den Knoten W, der vor V in P ist. Wenn die Strecke von S nach W kürzer als die Strecke von S nach V ist, ist P ein Alternativpfad zum Knoten V. Fahre bei Schritt 2 fort.
5. Erzeugen einer neuen Gruppe von Pfaden, die mit V beginnen und alle anderen Verbindungen verketten. Die Kosten sind die Summe der Kosten von P und der Verbindung die angehängt wurde. Einfügen der neuen Verbindung zu O und fortfahren mit Schritt 2.

Der Aufwand des Algorithmus ist O(N^2)

Psydocode

for all v <math> \in </math> V do
  g( v ) := 
  parent( v ) := nil
  done( v ) := false
g( s ) := 0
INIT( P )
Update( P , s , 0 )
while v := RemoveMin(P) != nil do
  done( v ) := true
  for all u = N+(v) do
    if done( u ) = false <math> \wedge </math> g( v ) + l(v,u) < g( u ) then
      g( u ) := g( v ) + l(u,v)
      parent( u ) := v
      Update( P , u , g( u ) )