我最近为我的项目添加了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