python实现最短路径代码

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

import heapq

def dijkstra(graph, start, end):
    # 初始化距离字典和前驱节点字典
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    predecessors = {node: None for node in graph}
    
    # 使用堆来存储未访问节点并按距离排序
    unvisited = [(0, start)]
    heapq.heapify(unvisited)
    
    while unvisited:
        # 取出距离最小的节点
        current_distance, current_node = heapq.heappop(unvisited)
        
        # 如果已经到达终点，返回最短距离和路径
        if current_node == end:
            path = []
            while current_node is not None:
                path.append(current_node)
                current_node = predecessors[current_node]
            path.reverse()
            return current_distance, path
        
        # 如果还未到达终点，更新相邻节点的距离
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_node
                heapq.heappush(unvisited, (distance, neighbor))
    
    # 如果无法到达终点，则返回None
    return None, None

其中，`graph`是一个字典，每个键表示一个节点，每个值是一个字典，表示该节点的相邻节点和对应的权重。`start`和`end`是起点和终点的节点。函数返回最短距离和路径。如果无法到达终点，则返回None。