3

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

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

4

2 回答 2

5

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

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

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

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

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

于 2009-09-12T03:59:40.760 回答
1

您也可以尝试给A* 算法一个旋转。

如果您可以使用良好的启发式方法，这种方法特别有用。

于 2012-01-26T14:06:59.937 回答