优化 Dijkstra 以获得密集图？
除了 Dijkstra 之外，还有其他方法可以计算近乎完整的图的最短路径吗？我有大约 8,000 个节点和大约 1800 万条边。我已经浏览了线程 “地图上的a到b”并决定使用Dijkstra。我使用 Boost::Graph 库在 Perl 中编写了脚本。但结果并不是我所期望的。使用调用 $graph->dijkstra_shortest_path($start_node,$end_node); 计算一条最短路径大约需要 10 多分钟。
我知道有很多优势，这可能是运行时间缓慢的原因。我是死在水里了吗？还有其他方法可以加快这个速度吗？
Is there another way to calculate the shortest path for a near complete graph other than Dijkstra? I have about 8,000 nodes and about 18 million edges. I've gone through the thread "a to b on map" and decided to use Dijkstra. I wrote my script in Perl using the Boost::Graph library. But the result isn't what I expected. It took about 10+ minutes to calculate one shortest path using the call $graph->dijkstra_shortest_path($start_node,$end_node);
I understand there are a lot of edges and it may be the reason behind the slow running time. Am I dead in the water? Is there any other way to speed this up?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
简短回答：如果您只想要一些最短路径，Dijkstra 算法是您的最佳选择；如果您想找到每对节点之间的最短路径，则 Floyd-Warshall 算法更好。
对于加权图，Dijkstra 算法可以找到从一个源到图中所有其他节点的最短路径。它在 O(V^2) 时间内对密集图进行操作。
Floyd-Warshall 找到所有节点对之间的最短路径。它需要密集的表示并在 O(V^3) 时间内运行。它在加权或未加权图上运行。
即使你的图很密集（根据你的问题的标题），如果你只想找到一些最短路径，将其转换为稀疏图并使用 Dijkstra 的稀疏实现可能会有一些好处。稀疏 Dijkstra 的运行时间为 O(E log V)。
请注意，这是假设所有边权重都是非负的；如果是，那么您就不能使用其中任何一个。您将不得不使用更慢的算法，例如贝尔曼-福特算法。
Short answer: Dijkstra's is your best bet if you want just a few shortest paths, and the Floyd-Warshall algorithm is better if you want to find the shortest paths between every pair of nodes.
Dijkstra's algorithm finds the shortest paths from one source to all other nodes in the graph, for weighted graphs. It operates on dense graphs in O(V^2) time.
Floyd-Warshall finds shortest paths between all pairs of nodes. It requires a dense representation and runs in O(V^3) time. It operates on weighted or unweighted graphs.
Even though your graph is dense (according to the title of your question), there might be some benefit to converting it to a sparse graph and using a sparse implementation of Dijkstra's if you just want to find a few shortest paths. Sparse Dijkstra's runs in O(E log V).
Please note that this is assuming that all your edge weights are non-negative; if they are, then you can't use any of these. You would have to use an even slower algorithm, like Bellman-Ford.
您还可以尝试尝试 A* 算法 。
如果您能够获得良好的启发式方法，那么这种方法尤其有用。
You could also try to give the A* algorithm a spin.
This approach is especially beneficial if you have access to good heuristics.