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

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 )

  Für K=alle noch nicht besuchten Nachbarknoten von Aktuell
    Dijkstra( K, Bisherige_Kosten + Kosten( Aktuell, K ) )

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.