bfs算法求单源最短路径代码

BFS（广度优先搜索）算法是一种用于寻找图中单源最短路径的算法。下面是一个简单的Python代码示例，实现了BFS算法来计算图中单源最短路径：

from collections import deque

# 用邻接表表示图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

def bfs_shortest_path(graph, start):
    queue = deque([start])
    visited = {start: None}

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited[neighbor] = node
                queue.append(neighbor)

    return visited

# 测试
start_node = 'A'
shortest_path = bfs_shortest_path(graph, start_node)

for node in shortest_path:
    if node is not None:
        print(f"Shortest path to {node}: ", end='')
        current_node = node
        while current_node:
            print(f"{current_node} <- ", end='')
            current_node = shortest_path[current_node]
        print(start_node)

这段代码首先定义了一个图的邻接表表示（graph），然后实现了一个bfs_shortest_path函数来计算单源最短路径。在该函数中，使用队列来遍历图中的节点，并使用一个字典visited来记录每个节点的前驱节点。最后，通过遍历visited字典来输出每个节点到起始节点的最短路径。