BFS是最佳搜索算法吗？

Question

我了解Dijkstra的算法，Floyd-Warshall算法和Bellman-Ford算法，用于查找图中2个顶点之间的最慢路径。

但是，当所有边的成本都相同时，最便宜的路径是边数最少的路径吗？我对吗？没有理由实施Dijkstra或Floyd-Warshall，最好的算法是从源头进行广度优先搜索，直到达到目标为止？在最坏的情况下，您将必须遍历所有顶点，所以复杂度是O（V）吗？有没有更好的解决方案？我对吗？

但是，互联网上有大量文章讨论了带障碍的网格中的最短路径，并且提到了Dijkstra或A *。即使在StackOverfow上- 查找最短路径，有障碍的算法，也可以在 这里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 算法的扩展（启发式函数是一个扩展）。

但是当所有边的成本都相同时，最便宜的路径是边数最少的路径吗？我对吗？

对。

没有理由实施 Dijkstra 或 Floyd-Warshall，最好的算法是广度优先搜索？我对吗？

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

那么，这些人都是傻子吗？还是我傻？为什么他们向初学者推荐像 Dijkstra 这样复杂的东西，他们只想在常规网格中将敌人移动到主角？

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

(...) 任何点（不包括 A 和 B）的捕获点都可能有障碍物阻碍路径，因此必须绕道。

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