用python实现Dijkstra算法

好的，下面是 Python 实现 Dijkstra 算法的示例代码：

import heapq

def dijkstra(graph, start):
    # 初始化距离为无穷大
    dist = {node: float('inf') for node in graph}
    # 起点距离为 0
    dist[start] = 0
    # 存储当前节点的前一个节点
    prev = {node: None for node in graph}
    # 用堆来实现优先队列
    pq = [(0, start)]
    
    while pq:
        # 取出距离最小的节点
        (min_dist, cur) = heapq.heappop(pq)
        # 如果当前节点已经被处理过，跳过
        if min_dist > dist[cur]:
            continue
        # 遍历当前节点的邻居节点
        for neighbor in graph[cur]:
            # 计算到邻居节点的距离
            distance = min_dist + graph[cur][neighbor]
            # 如果距离更短，更新距离和前一个节点
            if distance < dist[neighbor]:
                dist[neighbor] = distance
                prev[neighbor] = cur
                heapq.heappush(pq, (distance, neighbor))
    
    return dist, prev

其中，`graph` 是一个字典，用来表示图，键是节点，值是与该节点相邻的节点和对应的边权重。`start` 是起点节点。

执行 `dijkstra(graph, start)` 函数将返回两个字典，`dist` 字典表示从起点到各个节点的最短距离，`prev` 字典表示到达每个节点的前一个节点。