在寻路中，DFS和Dijkstra有什么区别？

Question

我正在研究 DFS 和 Dijkstra。在我的简单测试用例中，大多数都表明 DFS 更快。在我的测试用例中，通过每个节点的成本都是相同的。但大多数人在寻路时更喜欢 Dijkstra 而不是 DFS，因为 Dijkstra 非常准确。

那么，DFS 和 Dijkstra 有什么区别呢？另外，每种算法的优缺点是什么？

Answer 1

DFS 不断沿着节点跳跃，直到找到一条路径，而 Dijkstra 与 BFS 更相似，除了它跟踪权重（并非所有路径都具有相同的成本），并且会不断检查尚未检查的最短路径，直到到达目标。

一般来说，DFS（通常）是查找路径最快的方法，并且可以通过递归轻松实现，但 Dijkstra 算法是查找最短路径的最快通用方法。

在不太一般的情况下，有 A*，这是 Dijkstra 算法，上面有一些额外的启发式算法来猜测哪些路径可能更适合首先检查。这也将找到最短的可能路径，但如果您的启发式良好，可能会更快。

编辑：

我应该补充一点，如果你想快速找到一条“相当好的”路径，并且可以使用启发式方法，那么如果你的图表没有太多死胡同，那么带有启发式的 DFS 通常是一个不错的选择。这称为“贪婪最佳优先搜索”，是一种很好的、​​未充分利用的路径查找算法，可用于例如游戏（您可以将地图设计为几乎没有死胡同）或 A* 昂贵得令人望而却步的道路地图。