时间复杂度-双向Dijkstra算法

Question

我想了解双向Dijkstra算法的时间复杂度。

使用最小堆的普通Dijkstra算法是O(n log n + m)。我猜想双向算法的时间复杂度与之相同，但是维基百科表明，双向搜索的改进可以用O-Notation表示。

对于双向Dijkstra算法，是否也可以这样计算，如何计算？

- Denis Lukenich

Answer 1

基本上，双向方法的处理成本是半大小图的单向处理成本的两倍。对于暴力指数算法来说，这是一个巨大的收益（从O(m^n)到O(2*(m^n/2))）。 对于Djikstra算法而言，最坏情况基本相同。 然而，在这里评估效率的时间复杂度可能并不是最佳指标。 在像在道路网络上寻找路径这样的实际情况中，双向方法类似于在每个端点周围增加一个圆盘，并且当两个圆盘几乎相遇时停止，而单向方法则需要从起点开始增加一个圆盘，直到到达终点。 直觉上，如果R是起点和终点之间的直线距离，则直线搜索的成本为O(R^2)，而双向方法的成本为O(2*(R/2)^2)，即快2倍。 这篇论文很好地涵盖了这个主题。

无论如何，A*算法基本上是最好的选择，除非你正在探索一个没有有效估计启发式的搜索空间。

- kuroi neko

---

很棒的答案。我主要用它来处理道路网络，确实使用A-Star算法，或者如果我有机会进行一些预处理，则使用Contraction Hierarchies算法。 - Denis Lukenich

到目前为止，我只在计算挑战或类似视频游戏的代码中使用了A*算法，并且我发现双向搜索方法实现起来太过繁琐。有其他方法可以提高时间效率，特别是通过为估计距离启发式添加决策者（当移动到具有许多等效路径的图块时），或者像我所提到的论文中解释的那样，添加精心选择的辅助航点或预先计算的快捷方式。 - kuroi neko