单源最短路径dijkstra算法代码

以下是Dijkstra算法的Python代码，其中 graph 是一个字典，键是节点，值是它连接的节点及其权重。例如，如果节点A连接节点B和C，且权重分别为3和4，则 graph['A'] = [('B', 3), ('C', 4)]。

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        (dist, curr) = heapq.heappop(pq)
        if dist > distances[curr]:
            continue
        for (neighbor, weight) in graph[curr]:
            distance = dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

这个算法使用堆来维护一个优先队列，以确保在每次迭代中找到当前最短的路径。在初始化时，我们将起点的距离设置为0，其余的节点的距离设置为无穷大。

然后，我们使用堆来处理距离最小的节点。如果已知的距离比当前距离大，则跳过该节点。否则，更新该节点的距离并将其入堆。

最后，我们返回每个节点到起点的最短距离。