我最近为我的项目添加了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秒。我在任何文献中都找不到这种修改方法。很明显原因在于排序列表。插入/删除在具有10万个元素的情况下表现得比手头上少得多。
回答:
经过大量搜索我自己找到了答案。答案显然是:boost graph lib。真是太神奇了 - 我找了好一段时间都没有找到。如果你认为Dijkstra实现之间没有性能差异,请参见维基百科。
toDoList
的顺序是预先知道的,那么可以直接读出最短路径。关键是toDoList
应该是一个优先队列,元素在发现时添加。目标是创建一个最佳优先搜索,而第一个版本无法实现这一点。 - UnapiedraInsertAllNodes
做了什么,但如果它将源节点插入到 0 优先级,其余节点插入到 Infinity,那么它可能会工作,尽管速度较慢,因为队列必须无谓地处理所有顶点(加上已发现的顶点)。这时候,大 O 复杂度就真正得到了“实现”,因为队列始终处于其最大渐近大小。如果源节点和汇节点之间没有路径,则可以弹出汇节点(由InsertAllNodes
添加)并返回 Infinity 距离,而不是像第二个变体中那样耗尽队列。 - Adam