Dijkstra 算法的原理是什么？为什么不能处理负权边？

直接回答：Dijkstra 用贪心求单源最短路径：维护 dist 数组（初始源点 0、其余 ∞）和最小堆；每轮取出 dist 最小的未确定节点 u，把它标记为已确定，再用 u 松弛其所有邻边（dist[v] = min(dist[v], dist[u] + w(u,v))）。用二叉堆实现时间 O((V+E) log V)、空间 O(V)。

展开解析：不能处理负权边的原因在贪心依据：算法认定「当前 dist 最小的节点已收敛、不会再被更新」。若存在负权边，一条看似更长的路径可能经负边后变得更短，推翻已确定的值，算法却不回头。正确性证明（非负权下）用归纳：每次取出的 u 其 dist 已是全局最小估计，任何绕行路径都不优于它。工程细节：懒删除堆（允许堆中过期副本，取出时跳过已确定节点）比 decrease-key 实现简单；稠密图（E≈V²）用 O(V²) 朴素版反而更优。对比与追问：Bellman-Ford 可处理负权并能检测负环（O(VE)）、SPFA 是其队列优化但最坏仍 O(VE)、Floyd 求全源 O(V³)、A* 在已知终点方向时用启发函数剪枝。

示例：

import heapq

def dijkstra(adj, n, src):
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:          # 懒删除：跳过过期副本
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist