Dijikstra完整代码

Dijkstra算法是一种用于解决图中最短路径问题的贪心算法，以下是其完整的代码实现：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典和已访问节点集合
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    visited = set()
    
    # 使用堆优化的方式存储节点和距离信息
    heap = [(0, start)]
    
    while heap:
        # 取出距离最小的节点
        (distance, node) = heapq.heappop(heap)
        
        # 如果已经访问过该节点，则跳过
        if node in visited:
            continue
            
        # 标记为已访问
        visited.add(node)
        
        # 遍历该节点的所有邻居节点
        for neighbor, weight in graph[node].items():
            # 计算从起点到该邻居节点的距离
            dist = distance + weight
            
            # 如果计算出的距离比已有的距离更小，则更新距离字典和堆
            if dist < distances[neighbor]:
                distances[neighbor] = dist
                heapq.heappush(heap, (dist, neighbor))
                
    return distances

其中，`graph`参数是一个字典，表示图的邻接表；`start`参数是起点节点。算法返回一个距离字典，记录从起点到每个节点的最短距离。在实现中，使用了堆优化的方式来存储节点和距离信息，以提高算法的效率。