什么是最快的Dijkstra算法实现你知道（在C ++中）？你知道、算法、最快、Dijkstra

2023-09-12 21:16:57 作者：浅吟年华未央

我最近做附上Dijkstra算法的单源最短路径第3版到我的项目。

I did recently attach the 3rd version of Dijkstra algorithm for shortest path of single source into my project.

我认识到，有许多不同的实现而变化强烈的表现，也做不同的结果在很大程度上图的质量。随着我的数据集（> 100.000顶点）运行时从20分钟到几秒钟变化。钍最短路径也由1-2％之间。

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%.

这是你知道的最好的实现？

Which is the best implementation you know?

编辑：我的数据是液压网络，每个节点1至5个顶点。它相当于一个街道地图。我提出了一些修改一个已经加速算法（使用的排序列表的所有剩余节点），现在找到在时间的一小部分相同的结果。我已经寻找这样的事情很长一段时间。我不知道这样的实现已经存在。

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.

我无法解释的结果略有不同。我知道迪杰斯特拉不是启发式，但所有的实施方式似乎是正确的。更快的解决方案有结果更短的路径。我使用双precision数学专。

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.

编辑2：我发现，在被发现路径的差异确实是我的错。我已经插入特殊处理一些顶点（仅在一个方向有效），并忘了，在其他实施。

EDIT 2: 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.

但 IM仍然比吓一跳更多的Dijkstra算法可以通过下列变化显着加速：一般而言，Dijkstra算法包含了一个循环，如：

BUT im still more than surprised that Dijkstra can be accelerated dramatically by the following change: In general a Dijkstra algorithm contains a loop like:

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

如果你改变了这点，它的工作原理相同，但性能更好：

If you change this a little bit, it works the same, but performs better:

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元更糟糕的是一个完整的。

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.

答：

在很多谷歌上搜索我发现它自己。答案显然是： boost图LIB 。惊人的 - 我还没有发现这个相当长一段时间。如果你想，有Dijkstra算法实现之间没有性能差异，请参见维基。

After a lot of googling i found it myself. The answer is clearly: boost graph lib. Amazing - i had not found this for quite a while. If you think, that there is no performance variation between Dijkstra implementations, see wikipedia.

什么是最快的Dijkstra算法实现你知道（在C ++中）？你知道、算法、最快、Dijkstra

推荐答案