dijkstra算法的复杂度

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

Dijkstra算法用于计算单源最短路径问题，在不同实现方式下具有不同的时间复杂度。如果采用简单的邻接矩阵表示法并使用线性扫描寻找下一个最近节点，则该算法的时间复杂度为 \( O(n^2) \)[^1]。

然而，通过引入优先队列（如二叉堆）优化选取当前距离最小的顶点过程，可以使整体性能得到显著提升。在这种情况下，对于稀疏图而言，其平均情况下的渐近时间复杂度可降至 \( O((m+n)\log n) \)，这里\( m \)代表边的数量，而 \( n \) 是节点数[^4]。

值得注意的是，“复杂度”一词如果没有特别说明，默认指的是时间复杂度[^2]。

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

关于空间复杂度方面，主要取决于存储结构的选择以及额外辅助数据结构的需求。基本形式下，为了保存每个结点到起始结点之间的最短路径长度，至少需要占用与输入规模成比例的空间；同时还需要记录访问状态等信息。因此，基础版本的空间复杂度大约为 \( O(n) \)[^3]。

当应用高级的数据结构比如斐波那契堆来加速查找操作时，虽然能够进一步降低时间开销，但这也会相应增加一定的内存消耗，使得实际使用的总空间量有所增长。

import heapq

def dijkstra(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