在寻路方面，DFS和Dijkstra有什么不同？

Question

我在研究DFS和Dijkstra。在我的简单测试用例中，大多数都表明DFS更快。在我的测试用例中，传递每个节点的代价是相同的。但是大多数人更喜欢Dijkstra而不是DFS，因为Dijkstra是如此准确。

那么，DFS和Dijkstra有什么区别呢？还有，每种算法的利弊是什么？

Answer 1

DFS一直沿着节点跳转，直到找到一条路径，而Dijkstra更类似于BFS，除了它跟踪权重（不是所有路径的代价都相等），并且会一直检查尚未检查的最短路径，直到它到达目标。

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

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

编辑：

我应该补充一点，如果您想要一个“相当好”的路径在匆忙和启发式是可用的，如果您的图没有太多的死胡同，带有启发式的DFS通常是一个很好的选择。这被称为贪婪的最佳优先搜索，是一种很好的、未被充分利用的路径寻找算法，用于例如游戏中，在游戏中，你可以设计地图，使其几乎没有死角，或者在a*非常昂贵的情况下，路线图。