Dijkstra 算法优化

### Dijkstra算法优化技巧

对于Dijkstra算法而言，一种常见的优化方式是采用优先队列来减少时间复杂度。通过这种方式可以使得每次选取最短路径节点的操作更加高效[^1]。

当处理大规模图结构时，还可以利用启发式估计函数改进传统Dijkstra算法成为A*搜索算法，在保证找到最优解的同时提高效率[^2]。

另外一个重要方面是对数据存储结构的选择上做文章。例如使用斐波那契堆代替二叉最小堆作为优先级队列实现，可以在理论上获得更好的渐近性能提升[^3]。

import heapq

def dijkstra_optimized(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_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
                heapq.heappush(priority_queue, (distance, neighbor))
                
    return distances