数据结构 迪杰斯特拉算法实现

Dijkstra算法是一种最短路径算法，用于计算从起点到其他所有节点的最短路径。以下是一种基于堆的Dijkstra算法实现：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典和堆
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]

    while heap:
        # 取出堆顶节点
        current_distance, current_node = heapq.heappop(heap)

        # 如果当前节点的距离比已知最小距离大，则跳过
        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(heap, (distance, neighbor))

    return distances

其中，`graph`是一个邻接表形式的图，`start`是起点。在这个实现中，我们使用一个距离字典来记录每个节点到起点的最短距离，使用一个堆来存储待处理的节点。我们首先将起点的距离设置为0并加入堆中，然后不断进行以下操作：

1. 取出堆顶节点；
2. 如果当前节点的距离比已知最小距离大，则跳过；
3. 更新相邻节点的距离，并将其加入堆中。

最后返回距离字典即可。