Dijkstra-Algorithmus

Die Suche nach dem kürzesten (allgemein dem "besten") Weg zwischen zwei Knoten auf einem Graphen.

Algorithmus in sprachlicher Fassung

1. Markiere die Startstadt (rot einfärben), weise ihr die Kennzahl 0 zu. Bezeichne diese Stadt als aktuelle Stadt.
   
   
2. Suche alle Nachbarstädte der aktuellen Stadt, die selbst noch nicht aktuelle Stadt gewesen sind, und führe mit jeder folgendes durch:
   
   Errechne die Summe aus der Kennzahl der aktuellen Stadt und der Länge der Strecke von der Nachbarstadt zur aktuellen Stadt.
   
   
   • Hat die Nachbarstadt keine Kennzahl, weise ihr die Summe als Kennzahl zu und markiere die Verbindung zwischen Nachbarstadt und aktueller Stadt,
     
   • Hat die Nachbarstadt bereits eine Kennzahl kleiner als die Summe, mache nichts.
     
   • Hat die Nachbarstadt bereits eine Kennzahl größer als die Summe, ersetze die Kennzahl durch die errechnete Summe.
     Streiche die markierte Verbindung und markiere die Verbindung zwischen der Nachbarstadt und der aktuellen Stadt.
   
   
   
3. Markiere die Stadt mit der kleinsten Kennzahl, die noch nicht aktuelle Stadt gewesen ist, als neue aktuelle Stadt (rot einfärben). Weisen mehrere Städte dieselbe kleinste Kennzahl auf, wähle eine beliebige davon als aktuelle Stadt aus. Färbe die markierte Verbindung zur neuen aktuellen Stadt rot ein.
   
   
4. Solange es noch Städte gibt, die noch nicht aktuelle Stadt gewesen sind, gehe zu Schritt 2.

Aufwand

Die Problemgröße ist im Falle des Dijkstra-Algorithmus durch die Anzahl n der Städte auf der Landkarte (Knoten auf dem Graphen) gegeben. Aufwandsuntersuchungen beschäftigen sich immer mit der Frage, wie die Anzahl der Schritte, die ein Algorithmus abarbeiten muss, mit der Problemgröße wächst.

Brute-Force-Methode ("Holzhammer-Methode")

Nach der Brute-Force-Methode müssten zunächst alle Wege auf einem Graphen bestimmt, längenmäßig berechnet und miteinander verglichen werden. 

Sei n die Knotenzahl. Wir nehmen außerdem den schlimmsten Fall an, dass jeder Knoten mit jedem anderen Knoten des Graphen verbunden ist. Wir betrachten immer die Anzahl der Wege von einem beliebig gewählten Anfangs- zu einem beliebig gewählten Endknoten. 

• n = 2 : Es gibt w(2) = 1 Weg.
  
• n = 3 : Es gibt w(3) = 2 Wege.
• n = 4 : Vom neu hinzugekommenen Knoten gibt es drei Möglichkeiten des Anschlusses an den Graphen aus 3 Knoten. Entweder man trifft sofort den Zielknoten oder man landet bei einem Knoten, von dem aus es jeweils 2 Wege zum Zielknoten gibt. Das macht zusammen
  w(4) = 1 + 2 * w(3) = 1 + 2 * 2 = 5 Wege.
• n = 5 : w(5) = 1 + 3 * w(4) = 1 + 3 * 5 = 16 Wege.
• n = 6 : w(6) = 1 + 4 * w(5) = 1 + 4 * 16 = 65 Wege.
• n Knoten : 1 + (n-2) * w(n-1)
  

Die Wegezahl wächst exponentiell! Ein Algorithmus, der exponentiellen Aufwand verursacht, ist praktisch nicht einsetzbar, da er nur für wenige, kleine Werte Ergebnisse liefert.

Dijkstra

Der Algorithmus von Dijkstra führt im ersten Schritt - wenn wir wieder vom "worst case" ausgehen - n-1 Berechnungen durch. Danach ist die Startstadt aus dem Rennen und wird vom Algorithmus nie wieder angefasst. Allgemein ist im jeweils nächsten Schritt immer eine Berechnung weniger von Nöten. Insgesamt werden (n-1) + (n-2) + (n-3) + ... + 2 + 1 Berechnungen durchgeführt. Diese Summe lässt sich umformen:

(n-1) + (n-2) + (n-3) + ... + 2 + 1 = 1/2 * (n-1) * n = 1/2 * n² + 1/2 n

Man erkennt, dass sich die Schrittzahl als Wert einer quadratischen Funktion (allgemeiner Polynomfunktion) berechnet. Man spricht hier von polynomialen Aufwand.

» drucken: pdf | html