path - 为密集图优化 Dijkstra？

Question

除了 Dijkstra 之外，还有其他方法可以计算接近完整图的最短路径吗？我有大约 8,000 个节点和大约 1800 万条边。我已经完成了线程 "a to b on map"并决定使用 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)。

请注意，这是假设您所有的边权重都是非负的；如果是，则您不能使用其中任何一个。您将不得不使用更慢的算法，例如 Bellman-Ford。