堆优化下的dijkstra时间复杂度

### Dijkstra算法使用堆优化的时间复杂度分析

对于Dijkstra算法而言，当采用堆（优先队列）进行优化之后，其整体性能得到了显著提升。具体来说，在处理稀疏图的情况下，该版本的Dijkstra算法能够有效地减少不必要的计算开销。

在未经过任何优化的传统实现中，即所谓的朴素版Dijkstra算法，每次寻找当前距离最小节点的操作都需要遍历整个顶点集合，这使得总的时间消耗达到了O(n²)[^2]。然而，通过引入二叉堆或其他形式的支持高效提取最小值的数据结构作为优先级队列来替代这一过程，则可以大幅降低这部分操作的成本至O(log n)，其中n代表图中的节点数量。

因此，在考虑边的数量m以及节点数目n的前提下，利用堆优化后的Dijkstra算法执行一次完整的最短路径查找所需时间为：

- 插入或更新某个结点到已访问列表中的代价为O(log n)
- 对于每条边e=(u,v)，如果v还未被永久标记，则需尝试松弛这条边并可能调整对应的键值，此步同样涉及到了堆内元素位置的变化，故而也是O(log n)

综上所述，由于存在最多m次这样的边缘检查与潜在的位置变动，最终得到的整体时间复杂度变为O((m+n) log n)=O(m log n)[^1]。这里假设了图形较为稀疏的情况；而在极端情况下比如完全连通图时，尽管此时m≈n², 但因为实际应用中大多数场景下的网络并非如此密集连接，所以通常认为上述渐近表达式已经足够精确描述算法效率特性。

import heapq

def dijkstra_heap_optimized(graph, start_vertex):
    # 初始化单源起点和其他参数
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start_vertex] = 0
    
    priority_queue = [(0, start_vertex)]
    
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        if current_distance > distances[current_vertex]:
            continue
        
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
                
    return distances