迪杰斯特拉算法求校园导航最短路径程序设计代码实现

迪杰斯特拉(Dijkstra's Algorithm)是一种用于寻找图中两个节点之间的最短路径的经典算法。在校园导航场景中，我们可以将其应用于寻找两点之间的最短路径。下面是使用Python实现的一个简化版迪杰斯特拉算法的代码：

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    queue = [(0, start)]
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        if current_distance > distances[current_node]:
            continue  # 已经更新过更短的路径，跳过
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
                
    return distances

# 示例校园地图，用邻接字典表示（键为节点，值为字典，键值对为相邻节点和边的权重）
# graph = {
#     'A': {'B': 1, 'D': 4},
#     'B': {'A': 1, 'C': 2},
#     'C': {'B': 2, 'D': 1},
#     'D': {'A': 4, 'C': 1}
# }

# 初始化校园地图，比如以'起点'为起始点
start = 'A'
shortest_paths = dijkstra(graph, start)

print(f"从{start}到其他各点的最短路径距离为：")
for node, distance in shortest_paths.items():
    print(f"{node}: {distance}步")

#