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

Question

我想知道统一成本搜索和Dijkstra 算法之间有什么区别。它们似乎是相同的算法。

score 62 · Accepted Answer

Dijkstra 的算法，也许更广为人知，可以看作是统一成本搜索的一种变体，其中没有目标状态并且处理继续进行，直到所有节点都已从优先级队列中移除，即直到所有节点的最短路径 (不只是一个目标节点）已经确定

score 38 · Accepted Answer

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

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

score 22 · Accepted Answer

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

Dijkstra 算法找到从根节点到每个其他节点的最短路径。uniform cost 根据从根节点到目标节点的成本搜索最短路径。统一成本搜索是 Dijkstra 的算法，它专注于寻找到单个终点的最短路径，而不是到每个点的最短路径。

UCS 通过在找到终点后立即停止来实现这一点。对于 Dijkstra，没有目标状态，并且处理继续进行，直到所有节点都从优先级队列中移除，即直到确定了到所有节点（不仅仅是目标节点）的最短路径。

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

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

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

Djikstra 仅适用于将整个图作为输入的显式图。UCS 从源顶点开始，逐渐遍历图的必要部分。因此，它适用于显式图和隐式图（生成状态/节点的地方）。

score 4 · Accepted Answer

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

score 1 · Accepted Answer

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

5 回答 5