def dijkstra(start, end, graph): # 创建一个优先队列 queue = PriorityQueue() # 将起点添加到队列中 queue.put((0, start)) # 创建一个字典来存储每个节点的最短距离 distances = {start: 0} # 创建一个字典来存储每个节点的前一个节点 predecessors = {start: None} # 当队列不为空时 while not queue.empty(): # 取出队列中最小的节点 current = queue.get()[1] # 如果当前节点就是终点，则结束算法 if current == end: break # 遍历相邻节点 for neighbor in graph[current]: # 计算当前节点到相邻节点的距离 distance = distances[current] + neighbor[1] # 如果距离比之前计算的距离更短，则更新距离和前一个节点 if neighbor[0] not in distances or distance < distances[neighbor[0]]: distances[neighbor[0]] = distance predecessors[neighbor[0]] = current # 将相邻节点加入队列中 queue.put((distance, neighbor[0])) # 如果终点不在图中，则返回空列表 if end not in distances: return [] # 从终点开始追溯路径 path = [end] while path[-1] != start: path.append(predecessors[path[-1]]) # 反转路径，使其从起点到终点 path.reverse() return path

这是一个实现 Dijkstra 算法的 Python 代码。它用于计算有向加权图中从起点到终点的最短路径。算法使用了优先队列来实现。其中，distances 字典存储每个节点的最短距离，predecessors 字典存储每个节点的前一个节点，queue 是优先队列，用于存储待处理的节点。算法的时间复杂度为 O(E log V)，其中 E 是边的数量，V 是节点的数量。