c++ - 您所知道的最快的 Dijkstra 实现是什么(在 C++ 中)？

Question

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

我意识到有许多不同的实现，它们在性能上差别很大，而且在大型图形中的结果质量也确实不同。对于我的数据集(> 100.000 个顶点)，运行时间从 20 分钟到几秒不等。最短路径也有 1-2% 的差异。

您知道哪种实现方式最好？

编辑: 我的数据是一个水力网络，每个节点有 1 到 5 个顶点。它可与街道 map 相媲美。我对已经加速的算法进行了一些修改(对所有剩余节点使用排序列表)，现在在很短的时间内找到了相同的结果。我已经搜索了很长时间。我想知道这样的实现是否已经存在。

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

编辑 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 实现之间没有性能差异，请参阅 wikipedia .

Answer 1

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