dijkstra算法求最短路径代码

以下是使用Python实现Dijkstra算法求最短路径的代码：

import heapq

def dijkstra(graph, start):
    """
    :param graph: 图的邻接表表示
    :param start: 起点
    :return: 到各个点的最短距离
    """
    pq = []  # 优先队列，用于存储待遍历的节点
    heapq.heappush(pq, (0, start))  # 将起点加入队列
    dist = {start: 0}  # 存储到各个点的最短距离
    visited = set()  # 存储已访问的节点

    while pq:
        # 取出队列中距离起点最近的节点
        (distance, node) = heapq.heappop(pq)

        # 如果该节点已被访问过，则跳过
        if node in visited:
            continue

        # 标记该节点为已访问
        visited.add(node)

        # 遍历该节点的所有邻居节点
        for neighbor, weight in graph[node].items():
            # 计算到该邻居节点的距离
            distance_to_neighbor = distance + weight

            # 如果到该邻居节点的距离比之前计算的距离更短，则更新距离
            if neighbor not in dist or distance_to_neighbor < dist[neighbor]:
                dist[neighbor] = distance_to_neighbor
                # 将该邻居节点加入队列
                heapq.heappush(pq, (distance_to_neighbor, neighbor))

    return dist

其中，`graph`是以字典形式存储的图的邻接表表示，`start`是起点。函数返回一个字典，其中存储了从起点到各个点的最短距离。