优化 Dijkstra 以获得密集图？

Question

除了 Dijkstra 之外，还有其他方法可以计算近乎完整的图的最短路径吗？我有大约 8,000 个节点和大约 1800 万条边。我已经浏览了“地图上的 a 到 b”线程并决定使用 Dijkstra。我使用 Boost::Graph 库在 Perl 中编写了脚本。但结果并不是我所期望的。使用调用 $graph->dijkstra_shortest_path($start_node,$end_node); 计算一条最短路径大约需要 10 多分钟。

我知道有很多优势，这可能是运行时间缓慢的原因。我是死在水里了吗？还有其他方法可以加快这个速度吗？

Answer 1

简短回答：如果您只想要一些最短路径，Dijkstra 算法是您的最佳选择；如果您想找到每对节点之间的最短路径，则 Floyd-Warshall 算法更好。

• 对于加权图，Dijkstra 算法找到从一个源到图中所有其他节点的最短路径。它在 O(V^2) 时间内对密集图进行操作。

• Floyd-Warshall 找到所有节点对之间的最短路径。它需要密集的表示并在 O(V^3) 时间内运行。它在加权或未加权图表上运行。

即使你的图很密集（根据你的问题的标题），如果你只想找到一些最短路径，将其转换为稀疏图并使用 Dijkstra 的稀疏实现可能会有一些好处。稀疏 Dijkstra 的运行时间为 O(E log V)。

请注意，这是假设所有边权重都是非负的；如果是，那么您就不能使用其中任何一个。您将不得不使用更慢的算法，例如贝尔曼-福特算法。