如何用Python实现Dijkstra最短路径算法？

Dijkstra算法是一种用于寻找图中两点之间最短路径的经典算法。在Python中，我们可以使用字典数据结构来存储图的信息，并维护一个优先级队列来管理待处理的节点。以下是Dijkstra算法的基本步骤：

1. 创建一个空字典`dist`，其中键是所有节点，初始值都是无穷大，除了起点，其值设为0。
2. 创建一个空集合`visited`来记录已访问过的节点。
3. 初始化一个优先级队列`pq`，包含起点及其距离0。
4. 当队列非空时，取出当前距离最小的节点u。
5. 更新u的所有邻居v的距离，如果通过u到达v的距离比之前更小，则更新`dist[v]`并将其添加到`pq`中。
6. 遍历所有邻居后，标记节点u为已访问，移除它出`pq`。
7. 重复步骤4到6，直到队列为空。

下面是一个完整的Dijkstra算法实现示例：

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        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
                heapq.heappush(pq, (distance, neighbor))

    return distances

# 使用字典表示图，如：graph = {'A': {'B': 1, 'C': 4}, 'B': {'C': 2, 'D': 5}, 'C': {'D': 1}, 'D': {}}
start_node = 'A'
shortest_paths = dijkstra(graph, start_node)
print(shortest_paths)  # 返回各节点到起始点的最短距离