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

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.