python Dijkstra算法

Dijkstra算法是一种用于解决单源最短路径问题的经典算法，它可以找到从一个起点到其他所有节点的最短路径。下面是Python中实现Dijkstra算法的基本步骤：

1. 创建一个空的距离字典distances和一个空的前驱节点字典predecessors，用于存储每个节点的最短距离和前驱节点。
2. 将起点的最短距离设置为0，并将起点添加到一个优先队列中。
3. 当优先队列不为空时，重复以下步骤：
- 从优先队列中取出距离起点最近的节点，记为current。
- 遍历current的所有邻居节点，计算从起点到邻居节点的距离。如果该距离小于邻居节点当前的最短距离，则更新邻居节点的最短距离和前驱节点，并将邻居节点加入优先队列。
4. 完成后，distances字典中存储了起点到每个节点的最短距离，predecessors字典中存储了每个节点的前驱节点。

下面是一个简单的Python实现示例：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    predecessors = {node: None for node in graph}
    queue = [(0, start)]

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

        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
                predecessors[neighbor] = current_node
                heapq.heappush(queue, (distance, neighbor))

    return distances, predecessors

这段代码实现了Dijkstra算法，其中graph是一个字典，表示图的邻接表形式。每个节点作为键，对应的值是一个字典，表示与该节点相邻的节点及其边的权重。