python 广度优先搜索最短路径

在Python中，广度优先搜索(Breadth-First Search，简称BFS)是一种用于寻找图中两点之间最短路径的经典算法。BFS通常适用于无权图（边没有权重）或等权重图，因为它会按照节点的距离逐层遍历，首先访问距离起点最近的节点。

以下是使用Python实现BFS求解最短路径的基本步骤：

1. 创建一个队列，并将起始节点放入队列。
2. 初始化一个字典来存储每个节点到起始节点的距离，默认值为无穷大，起点的距离设为0。
3. 当队列不为空时，进行循环操作：
a. 从队列中取出当前节点。
b. 遍历该节点的所有邻居，对于每个未访问过的邻居，更新其距离为当前节点距离加一，并将其加入队列。
4. 最终，起点到其他所有节点的最短距离就是它们在距离字典中的值。

下面是一个简单的示例，假设我们有一个表示邻接关系的二维列表`adjacency_list`：

from collections import deque

def bfs_shortest_path(graph, start):
    queue = deque()
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue.append(start)

    while queue:
        current_node = queue.popleft()  # 取出队首节点
        for neighbor in graph[current_node]:
            new_distance = distances[current_node] + 1
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                queue.append(neighbor)

    return distances

# 使用示例：
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

start_node = 'A'
shortest_paths = bfs_shortest_path(graph, start_node)