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

我意识到，有许多不同的实现，它们的性能差异很大，并且在大型图中结果的质量也确实存在差异。使用我的数据集（>
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秒。在任何文献中都找不到这种修改。同样很清楚，原因在于排序列表中。插入/擦除操作会产生100.000个元素，而整手操作的效果要差得多。

回答：

经过大量的谷歌搜索后，我自己找到了它。答案很明显： boost graph
lib
。太神奇了-
我好久没有找到这个了。如果您认为Dijkstra实现之间的性能没有差异，请参阅Wikipedia。