是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到所有其他頂點的最短路徑。

迪傑斯特拉並不那麼複雜，即使是初學者也是如此。它通過BFS +來完成更多的事情。這更多的是存儲和更新有關到當前訪問頂點的最短路徑的信息。

如果你想找到2個頂點v和q之間的最短路徑，你可以通過修改Dijkstra來做到這一點。只要到達頂點q就停下來。

最後一個算法 - A *是最聰明的（也許是最困難的）。它使用啓發式的魔法仙女，它建議你去哪裏。如果你有一個很好的啓發式功能，這個算法勝過BFS和Dijkstra。 A *可以看作是Dijktra算法的擴展（啓發式函數是擴展）。

但是當所有的邊都具有相同的成本時，最便宜的路徑是邊數最少的路徑 ？我對嗎？

沒錯。

沒有理由實施Dijkstra或Floyd-Warshall，最好的 算法是廣度優先搜索？我對嗎？

當談到這樣一個簡單的情況下，所有的邊都有相同的重量 - 你可以使用任何你喜歡的方法，一切都會奏效。然而，具有良好啓發式的A *應該比BFS和Dijkstra更快。在你提到的simulation中，你可以觀察到。

那麼，這些人都是愚蠢的嗎？還是我愚蠢？爲什麼他們向初學者推薦如Dijkstra這樣複雜的東西，他們只是想將敵人移動到常規網格中的主角上？

他們有一個不同的問題，這改變了解決方案。仔細閱讀問題描述：

（...）美中不足的是任何點（不包括A和B）可以有一個 障礙阻礙路徑，從而必須繞道。

敵人在前往主角的途中可能會遇到障礙。所以，例如A *在這種情況下是一個不錯的選擇。

Answer 2

但是，當所有的邊具有相同的成本時，最便宜的路徑是邊數最少的路徑？。 是的

如果你真的瞭解你鏈接的文章，你會注意到他們想解決的問題與你的不同。

Answer 3

BFS就像是一個「蠻力」，可以在未加權的圖中找到最短路徑。 Dijkstra's就像是一個加權圖的「蠻力」。如果您要在未加權的圖上使用Dijkstra，那麼它將完全等同於BFS。

因此，Dijkstra's可以被認爲是BFS的延伸。這不是一個真正的「複雜」算法;它只比BFS稍微複雜一些。

A *是Dijkstra's的擴展，它使用heuristic來加速尋路。