dijkstra复杂度

### Dijkstra算法的时间复杂度分析

Dijkstra算法用于计算单源最短路径问题，在不同实现方式下具有不同的时间复杂度。当采用邻接矩阵表示法并使用简单的数组来追踪距离时，该算法的时间复杂度为 O(n²)，这里 n 表示顶点的数量[^3]。

如果利用优先队列优化，则可以在稀疏图上获得更好的性能表现。具体来说，对于含有 E 条边和 V 个节点的加权有向无环图(DAG), 使用斐波那契堆作为优先队列的数据结构可使时间复杂度降低至 O(E + V logV)[^2]。

### Dijkstra算法的空间复杂度分析

关于空间复杂度方面，主要取决于存储图形的方式以及辅助数据结构的选择。一般情况下，为了保存每个结点到起始结点之间的最短路径长度，需要额外开辟一个大小为 |V| 的一维数组；同时还需要记录哪些结点已经被访问过，这同样消耗线性的内存开销。因此，总体而言，Dijkstra算法的空间复杂度大约是 O(V) 或者说与顶点数成正比[^1]。

import heapq

def dijkstra(graph, start):
    pq = [(0, start)]  # priority queue with tuple (distance, node)
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    
    while pq:
        current_dist, u = heapq.heappop(pq)

        if current_dist > dist[u]:
            continue
        
        for v, weight in graph[u].items():
            distance = current_dist + weight
            
            if distance < dist[v]:
                dist[v] = distance
                heapq.heappush(pq, (distance, v))
                
    return dist