Dijkstra - Single source shortest paths
Testgebeit DGM triangulation Rheinausschnitt mit 2.7 Millionen Punkte und 8.1 Millionen Kanten. Das Gebiet ist in Nord Süd Richtung lang gestreckt und in Ost West Richtung schmal. Es soll ein kürzester Path von einem Startpunkt auf der Ostrand hin zur Westrand gefunden werden. Der überwiegende Teil des Gebiets muss im Vergleich zur Luftlinie dabei nicht durchlaufen werden.
Standard Dijkstra
Die Standard Variante von Dijkstra berechnet vom Startknoten zu jedem anderen Knoten im Mesh den kürzesten Path.
Beschleunigungstechnik Early Termination
Sobald der Zielknoten als finish markiert wird, beendet der Algorithmus. Muss vom Start zum Ziel, wie in diesem Beispiel, nicht das komplette Gebiet durchlaufen werden, ergibt diese Technik eine Beschleunigung.
Beschleunigungstechnik Bidirectional Search
Es kann eine zweite Suche vom Zielknoten hin zum Startknoten auf dem transponierten Graph gestartet werden. Die beiden Dijkstra Instanzen werden nicht parallel, sondern abwechseln angestoßen und iterieren je ein mal. Sobald ein Knoten von einer Suchinstanz als finish markiert wird, welche in der anderen Suchinstanz schon als finish markiert worden ist, terminiert der Algorithmus.
Der ausgegebene Path muss nicht zwangsläufig der kürzeste Path von s nach t sein. Es ist möglich, dass es einen kürzeren Path über eine Kante gibt, welche in beiden Suchinstanzen auf gesehene, aber noch nicht finished Knoten zeigt.
Laufzeiten: GCC 8.2 -O2 -funroll-loops AMD FX-8350 Eight-Core Processor 4 GHz
Standard Dijkstra 2.79 sec
Early Termination 1.19 sec speedup 2.3
Bidirectional Search 0.925 sec speedup 3.0
Created with GIMP
Created with GIMP