统一成本搜索和 Dijkstra 的算法有什么区别？

小开

有一篇论文讨论了两者的异同。

小开

Dijkstra 的算法，也许更为人所知，可以被认为是作为统一成本搜索的一种变体，其中没有目标状态和处理继续进行，直到从优先级队列，即直到到达所有节点的最短路径(而不仅仅是一个目标节点)已确定

小开

Dijkstra 的算法在图中搜索 从根到每个其他节点的最短路径，而统一成本搜索 按照到达目标节点的成本计算的最短路径。

此外，统一成本的空间需求较少，而优先级队列是“惰性”填充的，这与 Dijkstra 相反，Dijkstra 在启动时以无限成本将所有节点添加到队列中。

小开

NotAUser、 dreaMone 和 Bruno Calza 编辑的其他答案

Dijkstra 算法找到从根节点到其他节点的最短路径。根据从根节点到目标节点的代价，统一代价搜索最短路径。统一成本搜索是 Dijkstra 的一种算法，它主要是寻找一条到达某一终点的最短路径，而不是到达每一终点的最短路径。

UCS 通过在找到终点后立即停止来实现这一点。对于 Dijkstra，没有目标状态，处理继续进行，直到从优先级队列中删除所有节点，也就是说，直到确定到达所有节点的最短路径(不仅仅是一个目标节点)。

UCS 的空间需求较少，优先级队列是逐渐填充的，而 Dijkstra 的优先级队列在开始时以无限的成本将所有节点添加到队列中。

由于以上几点，Dijkstra 比 UCS 更耗时

UCS 通常用在树上，而 Dijkstra 用在一般图上

Djikstra 只适用于给出整个图作为输入的显式图。UCS 从源顶点开始，逐渐遍历图的必要部分。因此，它适用于显式图和隐式图(其中生成状态/节点)。

小开

主要的区别是，Dijkstra 的算法是在顶点数目有限时定义的。它说把所有的顶点放在一个队列中。但是当顶点的数目趋于无限时，我们不能把所有的顶点放在一个队列中。统一成本搜寻是在这样的情况下定义的，其中顶点的数量是未知的。