用python编写宽度优先搜索算法从杭州到哈尔滨的最短路径

为了演示如何使用Python编写宽度优先搜索（BFS）算法来找到从杭州到哈尔滨的最短路径，假设我们有一个简单的示例地图，其中城市作为图的节点，有直接连接的公路表示边。由于实际的城市交通网络通常更复杂，这里我们将简化处理。

首先，我们需要创建一个数据结构来表示图，比如使用邻接列表：

import numpy as np

# 城市图简化版，用二维数组表示邻接矩阵
adjacency_matrix = np.array([
    [0, 1, 0, 0, 0],
    [1, 0, 1, 0, 1],
    [0, 1, 0, 1, 0],
    [0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0]
], dtype=int)

# 杭州对应下标0，哈尔滨对应下标4
source_city = 0
destination_city = 4

# 转换为邻接表
cities = list(range(len(adjacency_matrix)))
connections = {city: [] for city in cities}
for i, row in enumerate(adjacency_matrix):
    for j, connection in enumerate(row):
        if connection != 0:
            connections[i].append(j)

# 定义BFS函数
def bfs_shortest_path(start, destination, connections):
    visited = [False] * len(connections)  # 初始化已访问节点
    queue = [(start, [])]  # 开始位置及其路径
    while queue:
        current_city, path = queue.pop(0)
        visited[current_city] = True

        if current_city == destination:
            return path + [current_city]

        for neighbor in connections[current_city]:
            if not visited[neighbor]:
                queue.append((neighbor, path + [current_city]))

    return None  # 没有路径到达目的地

shortest_path = bfs_shortest_path(source_city, destination_city, connections)
if shortest_path is not None:
    print(f"从杭州到哈尔滨的最短路径: {shortest_path}")
else:
    print("无法找到从杭州到哈尔滨的路径")