StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhat is the fastest Dijkstra implementation you know (in C++)?
text
Body
copied!<p>I did recently attach the 3rd version of Dijkstra algorithm for shortest path of single source into my project. </p> <p>I realize that there are many different implementations which vary strongly in performance and also do vary in the quality of result in large graphs. With my data set (> 100.000 vertices) the runtime varies from 20 minutes to a few seconds. Th shortest paths also vary by 1-2%.</p> <p>Which is the best implementation you know?</p> <p><strong>EDIT:</strong> My Data is a hydraulic network, with 1 to 5 vertices per node. Its comparable to a street map. I made some modifications to a already accelerated algorithm (using a sorted list for all remaining nodes) and now find to the same results in a fraction of time. I have searched for such a thing quite a while. I wonder if such a implementation already exists.</p> <p>I can not explain the slight differences in results. I know that Dijkstra is not heuristic, but all the implementations seem to be correct. The faster solutions have the results with shorter paths. I use double precision math exclusively.</p> <p><strong>EDIT 2:</strong> I found out that the differences in the found path are indeed my fault. I had inserted special handling for some vertices (only valid in one direction) and forgot about that in the other implementation.</p> <p><strong>BUT</strong> im still more than surprised that Dijkstra can be accelerated dramatically by the following change: In general a Dijkstra algorithm contains a loop like:</p> <pre><code>MyListType toDoList; // List sorted by smallest distance InsertAllNodes(toDoList); while(! toDoList.empty()) { MyNodeType *node = *toDoList.first(); toDoList.erase(toDoList.first()); ... } </code></pre> <p>If you change this a little bit, it works the same, but performs better:</p> <pre><code>MyListType toDoList; // List sorted by smallest distance toDoList.insert(startNode); while(! toDoList.empty()) { MyNodeType *node = *toDoList.first(); toDoList.erase(toDoList.first()); for(MyNeigborType *x = node.Neigbors; x != NULL; x++) { ... toDoList.insert(x->Node); } } </code></pre> <p>It seems, that this modification reduces the runtime by a order not of magnitude, but a order of exponent. It reduced my runtime form 30 Seconds to less than 2. I can not find this modification in any literature. It's also very clear that the reason lies in the sorted list. insert/erase performs much worse with 100.000 elements that with a hand full of.</p> <p><strong>ANSWER:</strong></p> <p>After a lot of googling i found it myself. The answer is clearly: <strong><a href="http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/dijkstra_shortest_paths.html" rel="noreferrer">boost graph lib</a></strong>. Amazing - i had not found this for quite a while. If you think, that there is no performance variation between Dijkstra implementations, see <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time" rel="noreferrer">wikipedia</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload