迪杰斯特拉算法求最短路径的python代码

迪杰斯特拉算法的Python实现通常使用堆（Priority Queue）来保持对未访问节点的高效排序。下面是一个基本的实现，假设我们的图是以字典表示的邻接权重矩阵：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典和前驱节点字典
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous_nodes = {start: None}

    # 使用堆来存储节点及其余量
    unvisited = [(0, start)]
    heapq.heapify(unvisited)

    while unvisited:
        # 提取当前最小距离的节点
        current_distance, current_node = heapq.heappop(unvisited)
        
        # 如果当前节点已经是最短路径，跳过
        if distances[current_node] < current_distance:
            continue
        
        # 遍历当前节点的所有邻居
        for neighbor, weight in graph[current_node].items():
            # 计算经过当前节点到达邻居的距离
            distance_to_neighbor = current_distance + weight
            
            # 如果发现新的更短路径，更新距离和前驱节点
            if distance_to_neighbor < distances[neighbor]:
                distances[neighbor] = distance_to_neighbor
                previous_nodes[neighbor] = current_node
                # 将邻居加入堆，以便下一轮处理
                heapq.heappush(unvisited, (distance_to_neighbor, neighbor))

    return distances, previous_nodes

# 示例：
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2},
    'C': {'A': 4, 'D': 8, 'E': 3},
    'D': {'B': 2, 'C': 8, 'E': 7},
    'E': {'C': 3, 'D': 7}
}
shortest_paths = dijkstra(graph, 'A')
print(f"Shortest paths from A to other nodes: {shortest_paths[0]}")
print(f"Previous nodes for shortest paths: {shortest_paths[1]}")

这个例子中，`graph`是一个键值对的字典，键是节点名，值是另一个字典，表示与该节点相邻的节点及其相应的边权重。`dijkstra`函数返回两个字典：一个是各节点到起点的最短距离，另一个是形成这些最短路径的前驱节点。