Dijkstra代码python

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

import heapq

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

    # 将起点加入堆中，并将其距离设置为0
    heap = [(0, start)]

    while heap:
        # 弹出堆中距离最小的节点
        current_distance, current_node = heapq.heappop(heap)

        # 如果当前节点的距离已经大于已知最短路径，则跳过
        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
                previous_nodes[neighbor] = current_node

                # 将邻居节点加入堆中
                heapq.heappush(heap, (distance, neighbor))

    return distances, previous_nodes

其中，graph是一个字典，表示图的邻接表。例如，如果有一条从节点A到节点B的边权为3的边，则graph['A']['B'] = 3。start是起点节点的名称。该函数返回两个字典，分别表示起点到各个节点的最短距离和各个节点的前驱节点。