Dijkstra 算法在寻找最短路径方面比 A* 算法更好吗？

Question

Dijkstra 算法在寻找最短路径方面比 A* 算法更好吗？

Answer 1

它并不擅长寻找最短路径。只要您对 A* 有一个可接受的启发式算法，它就会比 Dijkstra 更快地找到短路路径。

正如 Mehrad 在评论中指出的那样，如果你给它一个返回 0 的启发式函数，A* 就会降级为 Dijktras。

A* 的维基百科文章 有大量关于所有这些的好信息。

Answer 2

如果您想找到从给定源节点到图中所有节点的最短路径，Dijkstra 比 A* 更好，因为如果您不在特定目标处停止，Dijkstra 无论如何都会覆盖整个图。与简单的 Dijkstra A* 相比，A* 是一种面向目标的算法，因此需要知道源节点和目标节点。如果您想使用 A* 算法用 N 个节点覆盖整个图，您基本上必须从源节点运行该算法 N 次。

Dijkstra 也可能更适合查找从源节点到图形的许多目标的最短路径。根据目标的位置（尤其是距源的距离）、目标的数量 M、图表的大小、A* 启发式的质量，将会存在一些盈亏平衡点，其中运行 Dijkstra 的性能比运行更好或更低M 倍 A* 算法。

编辑：受到 Matthew 正确批评评论的启发，我稍微改了一下并添加了注释：

• Dijkstra 在寻找到所有节点的最短路径方面并不比 A* 更好。正确的是：不比 A* 差。
• 要找到到具有 A* 的所有节点的最短路径，需要将估计到目标节点的成本的函数设置为零（因为没有目标节点）。将估计到目标节点的成本的函数设置为零，使得 A* 与 Dijkstra 相同； Dijkstra 是 A* 的特例。 怀疑的，因为非零函数是 A* 的核心。）
• （如果函数设置为零，是否应该将该算法称为“A*”（而不仅仅是“Dijkstra”）是值得 到所有节点的最短路径，我们也可以说：Dijkstra 就足够了。 A* 的细化是没有必要的，并且对我们没有帮助。
• 最后一句话也适用于在图中进行搜索，例如：查找标记有特定标志且最接近给定源节点的节点。由于您事先不知道目标，因此不可能定义一个函数来估计搜索节点的成本，因此 A*（狭义的非零函数）不适用。