algorithm - 具有单一来源、单一目标点的修改后的 Dijkstra 和统一成本搜索之间有什么区别？

Question

如果我们将Dijkstra算法从“单一源点到所有节点的最短路径”修改为寻找“单一源点到单个目的点的最短路径”，那么这个修改后的Dijkstra算法和uniform cost search有什么区别呢？任何帮助将不胜感激。谢谢。

Answer 1

可以在 Dijkstra’s Algorithm versus Uniform Cost Search or a Case Against Dijkstra’s Algorithm 中看到对两种算法之间差异的很好剖析。 .我只是引用了 Arial Felner 的一些结论:

The two algorithms have many similarities and are logically equivalent. The most important similarity is that they expand exactly the same nodes and in exactly the same order.

正如我们所怀疑的，从理论的角度来看，这两种算法是等价的。

However, there are many differences between these algorithms as described in text books and taught in classes. The main difference is the identity of the nodes in the priority queue. In modified Dijkstra, all nodes are initially inserted into the queue. In UCS, nodes are inserted to the queue lazily during the search.

---

因此，

1. 在内存需求方面它们是不同的，UCS 的OPEN 比修改后的Dijkstra 的Q 小很多。在任何给定的时间步长，修改后的 Dijkstra 的内存需求都大于 UCS。
2. 就运行时间而言，同样的推理适用于操作OPEN 或Q 的时间开销。修改后的 Dijkstra 在操作这些结构时有更大的开销，因为它存储了 dist[] = ∞ 的节点，这些节点永远不会被扩展。相比之下，在 UCS 中，OPEN 仅包含 dist ≠ ∞ 的节点，即，仅包含逻辑上需要且可能被选择用于扩展的节点。

综上所述，UCS和修改后的Dijkstra在大O复杂度上是等价的，扩展相同的节点和相同的顺序，但从实用的角度来说UCS应该是首选而且它更在没有启发式信息的情况下处理单一来源 - 单一目的地问题时广泛使用。