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

Question

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

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

Answer 1

DFS 一直沿着节点跳跃，直到找到 a 路径，而 Dijkstra 更类似于 BFS，除了它会跟踪权重(并非所有路径都具有相同的成本)并会不断检查最短路径在到达目标之前尚未检查。

一般来说，DFS(通常)是找到路径的最快方法，并且可以很容易地通过递归实现，但是 Dijkstra 算法是找到最短路径的最快一般方法.

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

编辑:

我应该补充一点，如果您急需一条“相当不错”的路径并且可以使用启发式方法，那么如果您的图表没有太多死胡同，那么带有启发式方法的 DFS 通常是一个不错的选择。这叫做 Greedy Best First Search是一种很好的、​​未被充分利用的寻路算法，可用于例如游戏，您可以将 map 设计成几乎没有死胡同，或者 A* 非常昂贵的路线图。