Bfs算法求解單源最短路徑問題

BFS（廣度優先搜尋）是一種圖算法，可以用來解決單源最短路徑問題。在這種問題中，給定一個圖和一個特定的源節點，目標是找出從源節點到圖中其他每個節點的最短路徑。

下面是一個使用BFS求解單源最短路徑問題的簡單算法：

1. 初始化一個包含源節點的隊列。
2. 將源節點的距離設為0，其他節點的距離設為無窮大。
3. 重複以下步驟直到隊列為空：
   • 從隊列中取出一個節點。
   • 檢查這個節點的所有鄰居，如果它們的距離比現在的長，更新它們的距離。
   • 將這些鄰居節點加入隊列的尾部，並將它們的距離加1（因為它們比源節點多一層）。

以下是一個Python的實現示例：

from collections import deque

def bfs(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    queue = deque([source])

    while queue:
        u = queue.popleft()
        for v in graph[u]:
            alt = dist[u] + 1
            if dist[v] > alt:
                dist[v] = alt
                queue.append(v)

    return dist

# 示例圖形
graph = {
    'A': {'B': 1, 'C': 2},
    'B': {'A': 1, 'D': 2, 'C': 3},
    'C': {'A': 2, 'B': 3, 'F': 5},
    'D': {'B': 2, 'E': 3},
    'E': {'D': 3, 'F': 2},
    'F': {'C': 5, 'E': 2}
}

# 源節點
source = 'A'

# 執行BFS
dist = bfs(graph, source)

# 輸出最短路徑
for v in dist:
    if dist[v] != float('inf'):
        print(f"{source} to {v} : {dist[v]}")

這個示例輸出了從源節點'A'到圖中每個節點的最短路徑距離。

請注意，BFS是一種通用算法，可以用來解決許多不同的圖問題。在單源最短路徑問題中，它通常比深度優先搜尋（DFS）更有效，因為它不會重複訪問已經檢查過的節點。然而，BFS並不是解決所有圖的最短路徑問題的最佳方法，特別是在帶權圖中，當圖的特徵適合於Dijkstra算法時，Dijkstra算法通常會更高效。