迪利斯特拉算法的不足

### Dijkstra算法的局限性和缺点

#### 1. 负权边处理不当
当图中存在负权边时，Dijkstra算法无法正确计算最短路径。这主要是因为Dijkstra算法假设所有的边权重都是非负数，在这种情况下一旦某个节点被标记为已访问，则其最短路径被认为已经找到并固定下来[^1]。

#### 2. 时间复杂度较高
对于稠密图而言，原始版本的时间复杂度达到\( O(N^2) \)，其中N表示顶点的数量。尽管可以通过引入优先队列（如二叉堆）将时间复杂度降低至 \( O((M+N)\log N) \)[^2]，但对于非常大规模的数据集来说仍然不够高效。

#### 3. 不适合动态变化环境
如果网络拓扑结构频繁变动或者新加入/删除节点和边的情况较多的话,Dijkstra算法每次都需要重新运行一遍才能得到最新的最优解,效率低下.

import heapq

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

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