Dijkstra 最短路算法

Dijkstra 求解非负边权图的单源最短路。给定源点 $s$，维护距离估计 $d[v]$：已经找到的从 $s$ 到 $v$ 的最短路径长度；尚未找到路径时为无穷大。

松弛与贪心选择

初始化 $d[s]=0$，其他距离为无穷大。每次选择尚未确定且距离估计最小的顶点 $u$，确定其最短距离，再用它的出边更新邻居：

$$d[v]\gets\min(d[v],d[u]+w(u,v)).$$

这里累加的是从源点出发的整条路径长度。Prim 算法虽然也取最小值，但维护的是连接生成树的一条边的权值，两者不能混用。

正确性

假设已经确定的顶点距离均正确，当前选出 $u$。考虑从源点到 $u$ 的任意路径，令 $y$ 是路径上第一个尚未确定的顶点。它之前的顶点已经展开过，因此对 $y$ 的距离估计不超过这条路径到 $y$ 的前缀长度。

因为 $u$ 的距离估计最小，有 $d[u]\le d[y]$；又因为剩余边权非负，路径到 $u$ 的总长不小于其到 $y$ 的前缀长。因此任何路径都不会短于 $d[u]$，当前距离可以确定。

负边会破坏最后一步推理。例如 $s\to a$ 权值为 2、$s\to b$ 为 5、$b\to a$ 为 -4，提前确定 $a$ 的距离为 2 就会错过长度为 1 的路径。

堆实现

邻接表中的每项是 (终点, 权值)，顶点编号为 0..n-1。输入要求所有边权非负。

from heapq import heappop, heappush
from math import inf

def dijkstra(adj, source):
    dist = [inf] * len(adj)
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        distance, u = heappop(heap)
        if distance != dist[u]:
            continue  # 跳过已被更短路径替代的旧堆项
        for v, weight in adj[u]:
            candidate = distance + weight
            if candidate < dist[v]:
                dist[v] = candidate
                heappush(heap, (candidate, v))
    return dist

堆为空时，所有可达顶点已处理，不可达顶点仍为无穷大。零权边允许存在。无向图需把每条边存为两条有向边。

该懒删除实现最多产生 $O(m)$ 个堆项，时间为 $O(n+m\log(m+1))$，额外空间为 $O(n+m)$。简单图上可写成常见的 $O((n+m)\log n)$。朴素扫描最小距离的版本用 $O(n^2+m)$ 时间，在稠密图上也有价值。