用dijkstra求解最短路径及花费代码

以下是使用Dijkstra算法求解最短路径及花费的Python代码示例：

import heapq

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

    # 使用堆来进行贪心策略的选择
    heap = [(0, start)]

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

        # 如果当前节点已经处理过，则跳过
        if current_distance > distance[current_node]:
            continue

        # 遍历当前节点的所有邻居节点
        for neighbor, weight in graph[current_node].items():
            # 计算到邻居节点的距离
            new_distance = current_distance + weight

            # 如果新的距离比之前的距离更小，则更新距离和前驱节点
            if new_distance < distance[neighbor]:
                distance[neighbor] = new_distance
                predecessor[neighbor] = current_node
                heapq.heappush(heap, (new_distance, neighbor))

    return distance, predecessor


# 测试数据
graph = {
    'A': {'B': 2, 'C': 1},
    'B': {'A': 2, 'C': 3, 'D': 2},
    'C': {'A': 1, 'B': 3, 'D': 1},
    'D': {'B': 2, 'C': 1, 'E': 4},
    'E': {'D': 4}
}

# 使用Dijkstra算法求解最短路径及花费
distance, predecessor = dijkstra(graph, 'A')

# 输出结果
print("最短距离:", distance)
print("前驱节点:", predecessor)

在上述代码中，我们使用堆来进行贪心策略的选择。首先，我们初始化距离字典和前驱节点字典，将起始节点的距离设为0。然后，我们将起始节点压入堆中，并开始遍历堆。每次从堆中弹出距离最小的节点，然后遍历该节点的所有邻居节点。对于每个邻居节点，我们计算到该节点的距离，如果新的距离比之前的距离更小，则更新距离和前驱节点，并将邻居节点压入堆中。最后，当堆为空时，我们就得到了最短路径及花费。