如何在廣度優先搜索中快速找到最短路徑？

我正在使用廣度優先搜索來查找圖中的位置，並且我非常確定我的算法能夠正常工作，但是當我完成後，我一直在尋找最短路徑來找到結果。實質上，我可以使用BFS從我的起始位置到最終位置，但我不知道如何構建從結尾到開始的最短路徑。任何幫助，將不勝感激。如何在廣度優先搜索中快速找到最短路徑？

謝謝。

來源

2013-02-06 Bob John

找到兩點之間的最短路徑實際上包括找到這些點的問題，所以事實上，您已經擁有了一個可用的BFS，這使您不會接近最短路徑問題。對於最短路徑算法（A *，Dijkstra，Bellman-Ford等），您有很多選擇 - 所以請查看它們。 – congusbongus

我認爲OP在假定圖形未加權。 – templatetypedef

@Bob John，你需要指定圖形是否加權和/或定向。如果兩者都不是，那麼回溯BFS將爲您提供解決方案。請注意，可能有多條最短路徑（長度相等）。 – Adam

一個選項將是以下內容。創建某種方式將每個節點與「父」節點關聯起來（可能是一個散列表，或者可以通過向表示節點的任何類型添加「父」字段）。然後，每當你從隊列中取出一個節點u並且要將一個節點v添加到隊列中時，將v的父指針設置爲節點u。這標誌着你到達節點v的方式是遵循u的路徑，然後通過一條邊擴展路徑以得到v。

一旦你完成了這個並完成了你的BFS，你可以讀取通過從目標節點開始的最短路徑的反轉，然後重複跟隨父指針，直到返回到開始節點。一旦你有了這個，你可以扭轉這個路徑來找回實際的最短路徑。

希望這會有所幫助！

來源

2013-02-07 00:24:29 templatetypedef

這假定最短路徑是從初始BFS向後追溯，這通常是不正確的。 – congusbongus

@叢旭 - 當然。我認爲，由於OP首先使用BFS，圖形未加權，因此BFS確實找到了從源節點到每個目標節點的最短路徑。在加權圖中，您肯定會使用另一種算法（Dijkstra，Bellman-Ford等） – templatetypedef

+1優秀的答案。是否有可能用'null'來標記未訪問的節點，並用一個指向父節點的指針訪問節點（你必須在BFS中標記節點，對嗎？我是生鏽的）。 – Patrick87

如何在廣度優先搜索中快速找到最短路徑？

回答

相關問題