What is the fastest Dijkstra implementation you know (in C++)?

Question

I did recently attach the 3rd version of Dijkstra algorithm for shortest path of single source into my project.

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%.

Which is the best implementation you know?

EDIT: 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.

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.

EDIT 2: 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.

BUT im still more than surprised that Dijkstra can be accelerated dramatically by the following change: In general a Dijkstra algorithm contains a loop like:

MyListType toDoList; // List sorted by smallest distance 
InsertAllNodes(toDoList);
while(! toDoList.empty())
{
    MyNodeType *node = *toDoList.first();
    toDoList.erase(toDoList.first());
    ...
}

If you change this a little bit, it works the same, but performs better:

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);
    }
}

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.

ANSWER:

After a lot of googling i found it myself. The answer is clearly: boost graph lib. Amazing - i had not found this for quite a while. If you think, that there is no performance variation between Dijkstra implementations, see wikipedia.

Answer 1

It's going to depend on a lot of things. How much do you know about your input data? Is it dense, or sparse? That will change which versions of the algorithm are the fastest.

If it's dense, just use a matrix. If its sparse, you might want to look at more efficient data structures for finding the next closest vertex. If you have more information about your data set than just the graph connectivity, then see if a different algorithm would work better like A*.

Problem is, there isn't "one fastest" version of the algorithm.

Answer 2

The last time I checked, Dijkstra's Algorithm returns an optimal solution. All "true" implementations of Dijkstra's should return the same result each time.

Similarly, asymptotic analysis shows us that minor optimisations to particular implementations are not going to affect performance significantly as the input size increases.

Answer 3

May be I am not answering your question. My point is why to use Dijkstra when there are pretty much more efficient algorithms for your problem. If your graph fullfills the triangular property (it is an euclidian graph)

|ab| +|bc| > |ac|

(the distance from node a to node b plus distance from node b to node c is bigger than the distance from node a to node c) then you can apply the A* algorithm. This algorithm is pretty efficient. Otherwise consider using heuristics. The implementation is not the major issue. The algorithm to be used does matter.

Answer 4

The best implementations known for road networks (>1 million nodes) have query times expressed in microseconds. See for more details the 9th DIMACS Implementation Challenge(2006). Note that these are not simply Dijkstra, of course, as the whole point was to get results faster.