algorithm - 时间复杂度 - 双向 Dijkstra

Question

我想知道双向 Dijkstra 算法的时间复杂度。

使用最小堆的普通 Dijkstra 具有 O(n log n + m)。我的猜测是双向保持不变。然而Wikipedia建议一般而言，双向搜索的改进可以用 O-Notation 表示。

双向 Dijkstra 也可以计算吗？如何计算？

Answer 1

基本上，双向方法的成本是单向处理一半大小图的两倍。对于强力指数算法，这是一个巨大的 yield (从 O(mⁿ) 到 O(2*(m^n/2))。
对于 Djikstra，最坏的情况基本保持不变。

但是，时间复杂度可能不是评估效率的最佳指标。

在实际情况下，例如在道路网络上寻找路线，双向方法类似于在两端生长一个圆盘，并在两个圆盘相遇时(几乎)立即停止，而单向方法则需要生长一个圆盘从头到尾。

直觉上，如果 R 是起点和终点之间的直线距离，则直线搜索的成本将为 O(R²)，而双向方法的成本为 O(2*(R/2)²)，即快 2 倍。

this paper很好地涵盖了这个主题。

无论如何，A* 基本上是可行的方法，除非您正在探索没有可用的有效估计启发式的搜索空间。