dijkstra - BFS 是最好的搜索算法吗？

Question

我知道 Dijkstra 的算法、Floyd-Warshall 算法和 Bellman-Ford 算法，用于查找图中 2 个顶点之间的最便宜路径。

但是当所有边的成本都相同时，最便宜的路径是边数最少的路径吗？我对吗？没有理由实现 Dijkstra 或 Floyd-Warshall，最好的算法是从源头进行广度优先搜索，直到我们到达目标？在最坏的情况下，你将不得不遍历所有的顶点，所以复杂度是 O(V)？有没有更好的解决办法？我对吗？

但是互联网上有大量的文章讨论了在有障碍的网格中的最短路径，他们提到了 Dijkstra 或 A*。即使在 StackOverfow 上 - Algorithm to find the shortest path, with obstacles
或在这里 http://qiao.github.io/PathFinding.js/visual/

那么，这些人都是傻子吗？还是我傻？为什么他们向初学者推荐像 Dijkstra 这样复杂的东西，他们只想在常规网格中将敌人移动到主角？就像有人问如何在列表中找到最小数，你建议他实现堆排序，然后从排序数组中取出第一个元素。

Answer 1

BFS(广度优先搜索)只是一种遍历图的方法。它的目标是访问所有顶点。就这样。移动图形的另一种方式可以是例如 DFS。

Dijkstra 是一种算法，其目标是找到从给定顶点 v 到所有其他顶点的最短路径。

Dijkstra 并不复杂，即使对于初学者也是如此。它遍历图，使用 BFS + 做更多事情。这更多的是存储和更新有关当前访问的顶点的最短路径的信息。

如果你想找到 2 个顶点 v 和 q 之间的最短路径，你可以通过稍微修改 Dijkstra 来做到这一点。当你到达顶点 q 时停止。

最后一个算法 - A* 是最聪明的(也可能是最困难的)。它使用一种启发式的魔法仙女，它会建议你去哪里。如果你有一个很好的启发式函数，这个算法会胜过 BFS 和 Dijkstra。 A* 可以看作是 Dijktra 算法的扩展(启发式函数是一个扩展)。

But when all the edges have the same cost, the cheapest path is the path with minimal number of edges? Am I right?

对。

There is no reason to implement Dijkstra or Floyd-Warshall, the best algorithm is Breadth-First search? Am I right?

当涉及到所有边都具有相同权重的这种简单情况时 - 您可以使用任何您喜欢的方法，一切都会奏效。但是，具有良好启发式的 A* 应该比 BFS 和 Dijkstra 更快。在 simulation你提到过，你可以观察到。

So, are all those people stupid? Or am I stupid? Why do they recommend so complicated things like Dijkstra to beginners, who just want to move their enemies to the main character in a regular grid?

他们有一个不同的问题，这改变了解决方案。仔细阅读问题描述:

(...) The catch being any point (excluding A and B) can have an obstacle obstructing the path, and thus must be detoured.

敌人在通往主角的路上可能会遇到障碍。因此，例如在这种情况下，A* 是一个不错的选择。