Bfs最短路徑

BFS（廣度優先搜尋）是一種圖算法，可以用來尋找圖中兩個節點之間的最短路徑。BFS會從起始節點開始，探索所有直接連接的節點，然後再探索這些節點的直接連接的節點，以此類推，直到找到目標節點或探索完所有節點為止。

以下是BFS用來尋找最短路徑的基本步驟：

1. 初始化一個隊列，用來存放待探索的節點。
2. 將起始節點放入隊列中。
3. 重複以下步驟直到隊列為空或找到目標節點：
   • 從隊頭取出一個節點。
   • 如果該節點是目標節點，則停止算法並返回最短路徑。
   • 探索該節點的所有未訪問的鄰居，並將它們放入隊列中。
   • 更新每個鄰居節點的路徑長度，即從起始節點到該節點的路徑長度。

在BFS中，最短路徑通常通過在每個節點上賦予一個訪問標記和一個到起始節點的路徑長度來跟蹤。當算法訪問一個節點時，會標記它為已訪問，並將其到起始節點的路徑長度加1。這樣，當算法找到目標節點時，就可以通過追溯路徑長度來重建最短路徑。

BFS在有向圖和無向圖上都適用，並且在圖中沒有負邊權的情況下，可以確保找到的最短路徑是實際的最短路徑。然而，如果圖中有負邊權，BFS可能會找到局部最短路徑而非全局最短路徑。這種情況下，通常會使用Dijkstra's算法或A*算法來尋找帶有負邊權的最短路徑。