gpt4 book ai didi

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

转载 作者:可可西里 更新时间:2023-11-01 15:06:07 25 4
gpt4 key购买 nike

我最近确实将用于单源最短路径的第 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 .

最佳答案

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

关于c++ - 您所知道的最快的 Dijkstra 实现是什么(在 C++ 中)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/938338/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com