用dijkstra算法实现最短路径的计算代码

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

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}
    
    # 使用堆来实现优先队列
    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`, `C`，边权重分别为1, 2, 3，那么图的表示方式可以是：

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2},
    'C': {'A': 4, 'B': 2}
}

`start`是起点节点的名称。

该函数返回两个字典，`distances`表示每个节点到起点的最短距离，`previous_nodes`表示每个节点在最短路径上的前置节点。例如，如果要得到从起点到节点`X`的最短路径，可以按以下方式进行迭代：

path = []
node = 'X'
while node is not None:
    path.append(node)
    node = previous_nodes[node]
path.reverse()

这样，变量`path`就是一个列表，表示从起点到节点`X`的最短路径上所有的节点。