Dijkstra

Dijkstra ist eine spezielle Form des Pathfinding. Hier geht es darum, für beliebig viele Agenten (oder "interessierte" computergesteuerte Einheiten) den kürzesten Weg zu einem bestimmten Ziel zu finden. Dieser Algorithmus ähnelt sehr dem Sprichwort: "Alle Wege führen nach Rom".

Vorgehensweise

Ausgehend von Rom (oder einem beliebigen anderen Zielort) erhält ein Graph in alle Richtungen die Kostenangaben (bzw. die Anzahl der Knoten die durchlaufen wurden). Dieser rekursive Vorgang wird so lange durchgeführt bis alle Knoten die Kosten zum Ziel besitzen. Wenn man nun von einem konkreten Knoten zu dem vorgegebenen Ziel möchte, so muss man sich nur den Nachbarknoten mit dem geringsten Wert raus suchen.

Algorithmus

Erstellung des Graphen

Für diesen Algorithmus müssen die "Kosten_zum_Ziel"-Werte für alle Knoten mit dem maximalen Wert initialisiert werden (zB FFFF Hex für 16 Bit Integer ohne Vorzeichen).

Dijkstra( Knoten Aktuell, Integer Bisherige_Kosten )
  Wenn Bisherige_Kosten + Kosten( Aktuell, K ) < K.Kosten_zum_Ziel
    K.Kosten_zum_Ziel = Bisherige_Kosten + Kosten( Aktuell, K )

  Wenn Knoten Aktuell bisher noch nicht besucht wurde
    Für K=alle Nachbarknoten von Aktuell
      Dijkstra( K, Bisherige_Kosten + Kosten( Aktuell, K ) )

Die Abfrage "Knoten Aktuell bisher noch nicht besucht" kann entweder über einen eigenen boolean-Wert überprüft werden, oder aber durch einen speziellen Wert für die "Kosten_zum_Ziel" welcher maximial initialisiert wurde, also beispielsweise bei einem 16 Bit Integer ohne Vorzeichen mit FFFF Hex.

Die Erstellung des Graphen benötigt eine Laufzeit von O(n^2) wobei n die Anzahl der Knoten ist. Der Speicherbedarf für diesen Algorithmus (sowohl zur Generierung als auch die fertig generierte Tabelle) ist O(n).

Suchen eines Weges

Zum suchen eines Weges von einem gegebenen Startpunkt zum Ziel muss man wie bereits erwähnt für jeden Knoten den Nachbarknoten suchen, welcher am nähesten beim Ziel liegt. Dies geschieht folgendermaßen:

Suche_Weg( Knoten Aktuell )
  Wenn Aktuell.Kosten_zum_Ziel = 0
    Ziel gefunden

  Für K = Knoten mit den geringsten Kosten_zum_Ziel
    Suche_Weg( K )

Dieser Algorithmus besitzt eine maximale Laufzeit von O(t*v) wobei t die Tiefe (oder Entfernung) in Knoten des Zieles vom Startpunkt ist, und v der durchschnittliche Verzweigungsgrad des Graphen. Der Speicherbedarf für diesen Algorithmus ist im Idealfall O(1) bzw. O(t) um den gesamten Pfad vom Start bis zum Ziel zu speichern, jedoch benötigt man natürlich die Tabelle von vorher welche einen Speicherbedarf von O(n) besitzt.