Dijkstra算法 vs 统一代价搜索（时间复杂度）

Question

我的问题如下：根据不同的来源，Dijkstra算法只是一种统一代价搜索的变体。我们知道，Dijkstra算法可以找到源节点到所有目标节点（单源）的最短路径。然而，我们总是可以修改Dijkstra算法以查找起始状态和目标状态之间的最短路径（当目标状态从优先级队列中弹出时，我们只需停止）；但这样做，最坏情况仍将找到从起点到所有其他节点的最短路径（假设目标是图中最远的节点）。

如果我们使用最小优先级堆实现Dijkstra算法，运行时间将为O(V log V +E)，其中E是边数，V是顶点数。

由于统一代价搜索与Dijkstra相同（稍有不同的实现），因此UCS的运行时间应该类似于Dijkstra，对吗？但是，根据我的AI课程，统一代价搜索在最坏情况下是指数级的，并且需要O(b^{1 + [C*/ε]})的时间，其中C*是最优解的成本。（b是分支因子）

这两个算法如何相同，而它们具有不同的运行时间？运行时间相同，但我们看待它的方式不同吗？

我将非常感谢您的帮助：）谢谢

- John

Answer 1

运行时间是否相同，只是我们看待它的方式不同？

是的。在无限大的图上，可以使用统一代价搜索算法，而 Dijkstra 的原始算法永远无法终止。在这种情况下，定义复杂度时不能用 V 和 E 这两个参数，因为它们可能都是无穷大的，从而导致的大 O 表示毫无意义。

- Fred Foo

---

让我们坚持使用有限图（可能非常大，但仍然是有限的）。那么我该如何证明这两个算法具有相同的运行时间？ - John

@John：通过重写任一算法的伪代码，直到找到另一个算法。这可能有些棘手，因为Dijkstra通常用于存储在内存中的有限图，而UCS用于表示作为边生成函数的潜在无限图。 - Fred Foo

我同意你所说的，但在我的情况下，这是我想要证明的：给定一个城市地图（一个图形），我想证明两种算法寻找最优解的时间复杂度相同。 - John