使用BFS查找2個節點之間的最短路徑

Question

我是圖論新手，需要一點幫助。假設我們有一個具有定義的開始和結束vertext的圖。如何使用BFS在開始和結束頂點之間獲得最短路徑。

我已經寫了計算整個圖的最短路徑，但不知道如何實現它時，我想「限制樹」只始端之間的這些頂點的程序。

任何幫助，僞代碼，建議將不勝感激。

Answer 1

BFS算法得到圖中的一個頂點並從頂點到所有其他頂點計算最短路徑。當到達某個頂點時，BFS已經找到了它的最短路徑。所以如果你只需要到該頂點的最短路徑，你就不需要繼續算法。您應該在達到所需頂點時完成算法。