为稠密图优化Dijkstra？

Question

除了Dijkstra外，还有另外一种方法来计算近似完全图的最短路径吗？我有大约8,000个节点和大约1,800万个边缘。我已经浏览了“地图上的a至b”线程，并决定使用Dijkstra。我用Perl编写了我的脚本，使用的是Boost：：。但结果和我预期的不一样。使用调用$ 10+ ->Dijkstra最短路径($start_node，$end_node)计算一条最短路径花费了大约几分钟的时间；

我知道有很多的边缘，这可能是背后的原因，缓慢的运行时间。我死在水里了吗？还有其他方法来加速这件事吗？

Answer 1

简短的回答:如果你只想要几条最短的路径，Dijkstra是你最好的选择，而如果你想在每一对节点之间找到最短的路径，Floyd算法会更好。

• Dijkstra的算法为加权图寻找从一个源到图中所有其他节点的最短路径。它在O(V^2)时间内对稠密图进行运算。
• 弗洛伊德-沃尔将在所有节点对之间找到最短的路径。它需要一个密集的表示，并在O(V^3)时间内运行。它对加权图或非加权图进行运算。

即使您的图是密集的(根据您问题的标题)，如果您只想找到几条最短的路径，那么将其转换为稀疏图并使用Dijkstra的稀疏实现可能会有一些好处。稀疏Dijkstra在O(E log V)中运行。

请注意，这是假设所有的边缘权重都是非负的；如果是，那么您就不能使用这些。你必须使用更慢的算法，比如Bellman。

Answer 2

你也可以试着让一个转一下。

如果您可以使用好的启发式方法，这种方法尤其有益。