利用广度优先算法找出最短路径python有向图并给出图例

好的，针对你的问题，我再次给出 Python 代码实现，并附上图例展示。

假设我们有以下的有向图：

A -> B -> D -> E
 \         /
  -> C -> -

其中，每个节点表示一个城市，每条有向边表示两个城市之间的路线，边的权重表示路线的长度。

使用 Python 代码实现如下：

from collections import deque

# 定义有向图的邻接表表示
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'D': 2},
    'C': {'D': 1},
    'D': {'E': 3},
    'E': {}
}

# 定义广度优先算法求最短路径
def bfs_shortest_path(graph, start, end):
    queue = deque([(start, [start])])  # 使用双向队列，初始化为起点
    visited = set()  # 记录已访问的节点
    while queue:
        node, path = queue.popleft()  # 取出队列中的节点和路径
        if node not in visited:  # 如果节点没有被访问过
            visited.add(node)  # 标记为已访问
            if node == end:  # 如果找到了终点
                return path  # 返回路径
            for neighbor, weight in graph[node].items():  # 遍历邻居节点
                if neighbor not in visited:  # 如果邻居节点没有被访问过
                    queue.append((neighbor, path + [neighbor]))  # 将邻居节点加入队列，并记录路径
    return None  # 如果没有找到路径，返回 None

# 测试代码
start = 'A'
end = 'E'
shortest_path = bfs_shortest_path(graph, start, end)
if shortest_path:
    print(f"The shortest path from {start} to {end} is: {' -> '.join(shortest_path)}")
else:
    print(f"There is no path from {start} to {end}")

输出结果为：

The shortest path from A to E is: A -> B -> D -> E

因此，从城市 A 到城市 E 的最短路径为 A -> B -> D -> E，路线长度为 6。

希望这个例子能够帮助你理解如何利用广度优先算法找出最短路径，并提供了图例展示。