title: What is the fastest Dijkstra implementation you know (in C++)?
body: <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-&gt;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>