你所知道的最快的Dijkstra实现是什么(用C++)?

我最近确实将Dijkstra算法的第三个版本附加到了我的项目中,用于单源最短路径。

My Data是一个液压网络,每个节点有1到5个顶点。这相当于一张街道地图。我对已经加速的算法进行了一些修改(对所有剩余节点使用排序列表),现在在很短的时间内找到了相同的结果。我寻找这样的东西已经有一段时间了。我想知道这样的实施是否已经存在。

我无法解释结果中的细微差异。我知道Dijkstra不是启发式的,但所有的实现似乎都是正确的。更快的解决方案具有更短路径的结果。我只使用双精度数学。

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

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

看起来,这种修改将运行时间减少了一个数量级,而不是一个指数级。它将我的运行时间从30秒缩短到2秒以下。我在任何文献中都找不到这种修改。很明显,原因在于排序列表。插入/擦除在100000个元素时的性能要差得多,而用一只手装满。

boost graph lib wikipedia .