具有单一来源、单一目标点的修改后的 Dijkstra 和统一成本搜索之间有什么区别？
What's the difference between Modified Dijkstra with single source, single destination point and Uniform Cost Search?
如果我们从"single source to all nodes shortest path"修改Dijkstra算法，从"single source to a single destination point"找到最短路径，那么这个修改后的Dijkstra算法和uniform cost search有什么区别呢？任何帮助将不胜感激。谢谢。
没有区别。如果您使用 dijkstra，当您从单一源开始时，将计算所有节点的最短路径。您从源节点访问连接的节点。然后下一个节点是优先级队列中成本最短的节点。在将新节点插入优先级队列之前，检查当前节点成本和新节点成本。如果新成本小于节点成本，则将此节点插入优先队列。
查看this了解如何计算所有节点的单一来源。
在 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.
因此,
- 在内存需求上不同，UCS的OPEN比修改后的Dijkstra的Q小很多。在任何给定时间步长，修改后的 Dijkstra 的内存需求都大于 UCS。
- 就运行时间而言，同样的推理适用于操作OPEN或Q的时间开销。修改后的 Dijkstra 有更大的开销 来操纵这些结构，因为它存储了 dist[] = ∞ 的节点，这些节点永远不会被扩展。相比之下，在 UCS 中，OPEN 仅包含 dist ≠ ∞ 的节点，即 仅包含逻辑上需要且可能被选择用于扩展的节点 .
综上所述，UCS和修改后的Dijkstra在大O复杂度上是等价的，扩展相同的节点和相同的顺序，但是从实用的角度来说UCS应该是首选视图，并且在没有启发式信息的情况下处理单源 - 单目标问题时使用更广泛。
如果我们从"single source to all nodes shortest path"修改Dijkstra算法，从"single source to a single destination point"找到最短路径，那么这个修改后的Dijkstra算法和uniform cost search有什么区别呢？任何帮助将不胜感激。谢谢。
没有区别。如果您使用 dijkstra，当您从单一源开始时，将计算所有节点的最短路径。您从源节点访问连接的节点。然后下一个节点是优先级队列中成本最短的节点。在将新节点插入优先级队列之前，检查当前节点成本和新节点成本。如果新成本小于节点成本，则将此节点插入优先队列。
查看this了解如何计算所有节点的单一来源。
在 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.
因此,
- 在内存需求上不同，UCS的OPEN比修改后的Dijkstra的Q小很多。在任何给定时间步长，修改后的 Dijkstra 的内存需求都大于 UCS。
- 就运行时间而言，同样的推理适用于操作OPEN或Q的时间开销。修改后的 Dijkstra 有更大的开销 来操纵这些结构，因为它存储了 dist[] = ∞ 的节点，这些节点永远不会被扩展。相比之下，在 UCS 中，OPEN 仅包含 dist ≠ ∞ 的节点，即 仅包含逻辑上需要且可能被选择用于扩展的节点 .
综上所述，UCS和修改后的Dijkstra在大O复杂度上是等价的，扩展相同的节点和相同的顺序，但是从实用的角度来说UCS应该是首选视图，并且在没有启发式信息的情况下处理单源 - 单目标问题时使用更广泛。