4. Dijkstra算法精讲与实现

Dijkstra算法解决的是单源最短路径问题：给定一个带权有向或无向图，以及一个源点 s，求 s 到其余所有顶点的最短路径长度。它的核心前提是所有边权非负。这一限制并非可有可无的细节，而是算法正确性的根基——一旦出现负权边，贪心选择就可能失效，后面会具体说明。

算法的骨架可以用一句话概括：维护一个"已确定最短距离"的顶点集合 S，每轮从未确定的顶点中挑出当前距离估计值最小的那个，把它加入 S，并用它去"松弛"所有邻接边。这里的"距离估计值"记作 dist[v]，初始时 dist[s]=0，其余为 +∞。

贪心策略与松弛操作

贪心选择体现在"每轮取 dist 最小的未确定顶点"。为什么这样做是对的？直观理解是：由于边权非负，任何从源点出发、绕经其他未确定顶点再到达 u 的路径，长度都不会小于当前 dist[u]。因此当 u 成为未确定顶点中 dist 最小者时，dist[u] 已经不可能再被改小，可以安全地"定稿"。

松弛（relaxation）是更新距离的动作。对已确定顶点 u 的每条出边 (u, v, w)，若 dist[u] + w < dist[v]，则令 dist[v] = dist[u] + w，并记录前驱 pre[v] = u。松弛的本质是：尝试用"经过 u 的路径"去挑战"v 现有的最优估计"。前驱数组让算法不仅能给出距离，还能回溯出完整路径。

上图展示了一个示例图（边权为假设值）：s→a 权 4，s→b 权 2，a→u 权 3，b→u 权 5，u→c 权 6，u→d 权 1。按算法顺序，先确定 s（dist=0），松弛得 dist[a]=4、dist[b]=2；接着选 b（dist=2），松弛得 dist[u]=2+5=7；再选 a（dist=4），松弛得 dist[u]=min(7, 4+3)=7，不变；然后选 u（dist=7），松弛得 dist[c]=13、dist[d]=8。注意图中标注的 dist 值对应的是"u 被选中之前"的中间状态，用于说明松弛动作本身。

优先队列优化

朴素实现每轮线性扫描所有未确定顶点找最小值，复杂度 O(V²)。用优先队列（最小堆）可以把"取最小"降到 O(log V)。标准做法是惰性删除：不修改堆中已有元素，而是每次松弛成功就压入新的 (dist, v) 对；弹出时若该 dist 大于当前 dist[v]，说明是过期条目，直接丢弃。这样堆中最多有 O(E) 个元素，总复杂度 O((V+E) log V)。

import heapq

def dijkstra(graph, s, n):
    # graph[u] = [(v, w), ...]，边权均非负
    INF = float('inf')
    dist = [INF] * n
    pre = [-1] * n
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:        # 过期条目，跳过
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                pre[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, pre

def build_path(pre, s, t):
    path, cur = [], t
    while cur != -1:
        path.append(cur)
        cur = pre[cur]
    return path[::-1] if path[-1] == s else []

这段代码有两个易错点。第一，if d > dist[u]: continue 不能省，否则过期条目会导致重复松弛，虽不影响正确性但会拖慢速度。第二，Python 的 heapq 是最小堆，若用 C++ 的 priority_queue 需写成 greater<pair<int,int>> 或存负值。另外，若图是稠密图（E 接近 V²），O(V²) 的朴素数组实现反而常数更小，未必更慢。

正确性证明思路

用反证法。设算法第一次选出的"错误"顶点为 u，即 dist[u] 大于真实最短距离 d(u)。考虑 s 到 u 的真实最短路径，沿路径从 s 出发，设 x 是路径上第一个尚未被确定、且其前驱已被确定的顶点。由于边权非负，dist[x] 此时已等于 d(x)（前驱已确定并松弛过），且 d(x) ≤ d(u) < dist[u]。那么算法本轮应当选中 x 而非 u，矛盾。因此每次选出的顶点距离都是正确的，归纳可得全部正确。

复杂度与测试验证

复杂度小结：朴素数组实现 O(V²)，二叉堆实现 O((V+E) log V)，斐波那契堆理论可达 O(E + V log V)。空间上 dist、pre 各 O(V)，堆 O(E)。

测试时建议覆盖四类用例：单点图（只有 s）、不连通图（部分 dist 为 ∞）、含平行边与自环的图、以及随机图与暴力 Floyd 结果对拍。下面是一个可直接运行的断言测试：

g = [[] for _ in range(6)]
edges = [(0,1,4),(0,2,2),(1,3,3),(2,3,5),(3,4,6),(3,5,1)]
for u, v, w in edges:
    g[u].append((v, w)); g[v].append((u, w))  # 无向图

dist, pre = dijkstra(g, 0, 6)
assert dist == [0, 4, 2, 7, 13, 8], dist
assert build_path(pre, 0, 5) == [0, 2, 3, 5]
print("通过")

若断言失败，优先检查三处：边是否按无向/有向正确建图、INF 是否足够大（用 float('inf') 最稳妥）、以及路径回溯时 pre[s] 是否为 -1。运行输出"通过"即说明距离与前驱均符合预期，算法实现可用。