python实现dijkstra算法

以下是Python实现Dijkstra算法的代码：

import heapq

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

    # 用堆来实现优先队列
    pq = [(0, start)]
    while len(pq) > 0:
        # 取出堆顶元素
        current_distance, current_node = heapq.heappop(pq)

        # 如果当前节点已经被处理过了，就跳过
        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
                predecessors[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))

    # 返回最短路径和距离
    path = []
    current_node = end
    while current_node is not None:
        path.insert(0, current_node)
        current_node = predecessors[current_node]

    return path, distances[end]

该函数接受一个字典类型的图，起点和终点作为输入，返回最短路径和距离。其中，图的格式为{节点1: {邻居1: 权重1, 邻居2: 权重2, ...}, 节点2: {...}, ...}。该函数使用堆来实现优先队列，以提高效率。