你知道的最快的Dijkstra实现是什么(在C++中)？

Question

我最近做了第三版Dijkstra算法,将单一来源的最短路径附加到我的项目中.

我意识到有许多不同的实现在性能上有很大差异,并且在大图中的结果质量也有所不同.使用我的数据集(> 100.000个顶点),运行时间从20分钟到几秒不等.最短路径也变化1-2%.

你知道哪个是最好的实现？

编辑: 我的数据是一个液压网络,每个节点有1到5个顶点.它可以与街道地图相媲美.我对已经加速的算法做了一些修改(使用所有剩余节点的排序列表),现在在一小部分时间内找到相同的结果.我已经搜索了这样的事情了很长一段时间.我想知道这样的实现是否已经存在.

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

编辑2: 我发现找到的路径的差异确实是我的错.我已经为某些顶点插入了特殊处理(仅在一个方向上有效),并在其他实现中忘记了这一点.

但是我仍然惊讶于Dijkstra可以通过以下变化大幅加速:一般来说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.我在任何文献中都找不到这种修改.同样非常清楚的是,原因在于排序列表.插入/擦除在100.000元素的情况下执行得更糟糕.

回答:

经过大量的谷歌搜索后,我发现了自己.答案很清楚: boost graph lib.太棒了 - 我有一段时间没有找到这个.如果您认为Dijkstra实现之间没有性能差异,请参阅维基百科.

Answer 1

道路网络(> 100万个节点)的最佳实现具有以微秒表示的查询时间.有关第9次DIMACS实施挑战(2006)的详细信息,请参阅.请注意,这些不仅仅是Dijkstra,当然,重点是让结果更快.