![\"rheinmodellumgriff3\"](\"http:\/\/roboblog.fatal-fury.de\/wp-content\/uploads\/2019\/12\/rheinmodellumgriff3.jpg\")
<\/a><\/p>\nDijkstra - Single source shortest paths<\/p>\n
Testgebeit DGM triangulation Rheinausschnitt mit 2.7 Millionen Punkte und 8.1 Millionen Kanten. Das Gebiet ist in Nord S\u00fcd Richtung lang gestreckt und in Ost West Richtung schmal. Es soll ein k\u00fcrzester Path von einem Startpunkt auf der Ostrand hin zur Westrand gefunden werden. Der \u00fcberwiegende Teil des Gebiets muss im Vergleich zur Luftlinie dabei nicht durchlaufen werden.<\/p>\n
Standard Dijkstra
\nDie Standard Variante von Dijkstra berechnet vom Startknoten zu jedem anderen Knoten im Mesh den k\u00fcrzesten Path.<\/p>\n
Beschleunigungstechnik Early Termination
\nSobald 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.<\/p>\n
Beschleunigungstechnik Bidirectional Search
\nEs 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\u00dfen 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.
\nDer ausgegebene Path muss nicht zwangsl\u00e4ufig der k\u00fcrzeste Path von s nach t sein. Es ist m\u00f6glich, dass es einen k\u00fcrzeren Path \u00fcber eine Kante gibt, welche in beiden Suchinstanzen auf gesehene, aber noch nicht finished Knoten zeigt. <\/p>\n
Laufzeiten: GCC 8.2 -O2 -funroll-loops AMD FX-8350 Eight-Core Processor 4 GHz
\nStandard Dijkstra 2.79 sec
\nEarly Termination 1.19 sec speedup 2.3
\nBidirectional Search 0.925 sec speedup 3.0<\/p>\n