Pfadfindung: Dijkstra-Algorithmus

Eines der bekanntesten und vor allem effizientesten Algorithmen zur Bestimmung des kürzesten Pfad zwischen zwei Punkte eines Graphen ist der Dijkstra-Algorithmus. Normalerweise wird es so formuliert, dass der kürzeste Weg von einem Startknoten zu allen anderen Knoten in einem Graphen ermittelt wird, in diesem Fall wird jedoch zur Verdeutlichung ein Zielknoten eingeführt.

Aufgepasst: Der Algorithmus scheitert bei Graphen mit negativen Kantengewichten.

Prozess

Ausgangslage

Gegeben ist ein gewichteter Graph mit:

  • Knoten: Punkt
  • Kante: Verbindungen zwischen Knoten mit einer bestimmten Länge/Gewichtung
  • Start- und Zielknoten: Anfangs- und Endpunkt

Jeder Knoten enthält drei Eigenschaften:

  • Distanz: Summe der Distanz bis zum Startknoten (Anfangs unendlich)
  • Vorgänger: Vorherigen Knoten des bisherigen kürzesten bekannten Pfad (Anfangs leer)
  • Besucht: Ob der Knoten bereits verarbeitet wurde.

Zusätzliche Hilfsstrukturen:

  • Zu besuchende Knoten: Warteschlange aus Knoten der Distanz aufsteigend sortiert.
  • Zeiger: Aktueller zu bearbeitenden Knoten.

Algorithmus

  1. Setze die Distanz des Startknotens zu 0 und füge es der Warteschlange zu.
  2. Entferne einen Knoten aus der Warteschlange (automatisch derjenige mit der kürzesten Entfernung), weise es dem Zeiger zu und markiere es als besucht.
  3. Der Vorgang darf terminiert werden, sobald der Zeiger dem Endknoten entspricht.
  4. Für jeden unbesuchten Nachbarn des Zeigers:
    • Berechne eine neue mögliche Distanz: \(d_{neu} = \text{Distanz des Zeigers} + \text{Kantenlänge}\)
      • Ist die neue Distanz (\(d_{neu}\)) kleiner als die gespeicherte Distanz des Nachbars, setze diesem den Zeiger als Vorgänger, weise den neuen berechneten Distanzwert zu und, zum Schluss, aktualisiere den Knoten in der Warteschlange (oder füge es hinzu, falls es nicht bereits vorhanden ist).
  5. Wiederhole Schritt 2 bis die Warteschlange leer ist.
  6. Nun kann der kürzeste Weg über die jeweiligen Vorgänger zurückgelegt werden.

Beispiel

Eine hilfreiche Visualisierung des Dijkstra-Algorithmus kann im dem untenstehenden Link gefunden werden.

In diesem Tool wird der Graph zufällig generiert, wobei die Knoten als "Vertexes", besucht als "Known", Distanz als "Cost" und der Vorgänger als „Path“ bezeichnet werden.

Um den Algorithmus auszuführen, geben Sie die numerische ID des Startvertex in das Feld „Start Vertex“ ein und klicken Sie auf „Run Dijkstra“.

Visualisierungs-Webseite: https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html