问题描述

对每个顶点 vv，求最短距离 δ(v)\delta(v)（从 ss 到 vv 的最小路径长度）及其前驱。

算法思想

每次把“当前估计距离最小”的未确定顶点“封口”（settle），用它去松弛邻边；由于边非负，被封口的点已经“没法再更短”了。

输入：有向图 G=(V,E,W)，V={1,2,…,n}，S=1G=(V,E,W)，V=\{1,2,\ldots,n\}，S=1

输出：从 SS 到每个顶点的最短路径。

算法：

初始化 S={1}S=\{1\};

对于 i∈V−Si\in V-S ，计算从 11 到 ii 的相对 SS 的最短路，长度 dist⁡[i]\operatorname{dist}[i];

选择 j=min⁡v∈V−Sdist⁡[v]j=\min_{v\in V- S}\operatorname{dist}[v]，将 jj 加入 SS 并更新 V−SV-S 中顶点的 dist⁡\operatorname{dist};

重复上述过程，直到 S=V S=V.

正确性证明

记

  • δ(v)\delta(v)：ss到vv的真实最短路长度。

  • d[v]d[v]：当前算法中对 δ(v)\delta(v) 的估计。

  • SS：已“封口”的顶点集合（从队列里弹出、确定了的点）。

不变式（每次从优先队列取最小 dd 的点 uu 加入 SS 前后都成立）：

  1. 对所有 x∈Sx\in S，有 d[x]=δ(x)d[x]=\delta(x)（已确定的距离是真的）。

  2. 对所有 y∉Sy\notin S，d[y]d[y] 等于“内部点都在 SS 的从 ss 到 yy 的最短路”的长度；因此 δ(y)≤d[y]\delta(y) \le d[y]。

初始化：d[s]=0d[s]=0，其余 d=∞d=\infty，S=∅S=\varnothing。显然成立。

保持性：

假设不变量在本轮之前成立。令 uu 为队列中 dd 最小者，本轮把 uu 加入 SS 。要证 d[u]=δ(u)d[u]=\delta(u)。

取从 ss 到 uu 的一条真正最短路，令 yy 为该路上第一个不在SS的点，xx 为其前驱（在 SS）。

由不变式 1) 知 d[x]=δ(x)d[x]=\delta(x)。在 xx 被“封口”时我们松弛了(x,y)(x,y)，得到：

d[y]≤d[x]+w(x,y)=δ(x)+w(x,y)=δ(y)d[y]\le d[x]+w(x,y)=\delta(x)+w(x,y)=\delta(y)

因边非负，δ(y)≤δ(u)\delta(y)\le \delta(u)。

而队列里 d[u]d[u] 是最小的，所以 d[u]≤d[y]d[u]\le d[y]。

故我们得到：

d[u]≤d[y]≤δ(y)≤δ(u)d[u] \le d[y] \le \delta(y) \le \delta(u)

同时结合 δ(u)≤d[u]\delta(u) \le d[u]，有 d[u]=δ(u)d[u]=\delta(u)

即加入SS后不变式 1) 继续成立；松弛 uu 的出边只会把外部顶点的“内部在 SS 的最短路”更新为更短，故 2) 也保持。

终止：队列空或所有可达点都封口时，所有可达顶点 vv 满足 d[v]=δ(v)d[v]=\delta(v)。证毕。
要点：非负权保证“先确定的不会被后面更短的边翻盘”。

伪代码

# 输入：邻接表 G[u] = [(v, w), ...]，边权 w >= 0，源点 s
def dijkstra(G, s):
    for v in G:                 # 初始化
        d[v] = +∞
        parent[v] = None
    d[s] = 0

    # 小根堆里放 (当前估计距离, 顶点)
    heap = [(0, s)]
    settled = set()

    while heap:
        du, u = heappop(heap)
        if u in settled:        # 惰性删除：跳过过期条目
            continue
        settled.add(u)

        for v, w in G[u]:       # 松弛 u 的每条出边
            if v in settled: 
                continue
            if d[v] > du + w:
                d[v] = du + w
                parent[v] = u
                heappush(heap, (d[v], v))

    return d, parent            # d[v]=∞ 表示 v 不可达

时间复杂度

设 ∣V∣=n,∣E∣=m|V|=n, |E|=m

  • 用二叉堆：每条边最多触发一次成功松弛并向堆里推一次，代价 O(log⁡n)O(\log n)；再加上最多 nn 次弹出最小。总体O((n+m)logn)\mathcal{O}((n+m)logn)（适合稀疏图）

  • 若用邻接矩阵 + 线性扫描找最小：每轮找最小 O(n)O(n)，共 nn 轮，外加松弛 O(n2)O(n^2)，总体 O(n2)O(n^2)（适合稠密图）。

前提限制：若存在负权边，Dijkstra 可能错误；应改用 Bellman–Ford 或 Johnson 重赋权后再跑 Dijkstra。

例题

构造邻接表

  • 1→2(10), 1→6(3)

  • 2→3(7), 2→4(5)

  • 4→1(3), 4→3(4), 4→5(7)

  • 6→2(2), 6→4(6), 6→5(1)

从源点 1 用 Dijkstra，逐步把“当前距离最小”的点加入集合 SS 并松弛它的出边。记录 dist[]dist[] 与前驱 prev[]prev[] 。

初始化

  • S=∅S=\varnothing

  • dist[1]=0；其它 dist=∞；prev[*]=None

为方便阅读，下方用向量顺序 [1,2,3,4,5,6] 展示 dist，并列出本步选取的顶点与松弛更新。

步骤1：选 1（最小），加入 S

  • 松弛 1→2：dist[2] = min(∞, 0+10) = 10，prev[2]=1

  • 松弛 1→6：dist[6] = min(∞, 0+3) = 3， prev[6]=1

  • dist = [0,10,∞,∞,∞,3]，S={1}S=\{1\}

步骤2：选 6（当前最小3），加入 S

  • 6→2：dist[2] = min(10, 3+2) = 5，prev[2]=6（更新）

  • 6→4：dist[4] = min(∞, 3+6) = 9， prev[4]=6

  • 6→5：dist[5] = min(∞, 3+1) = 4， prev[5]=6

  • dist = [0,5,∞,9,4,3]，S={1,6}S=\{1,6\}

步骤3：选 5（4），加入 S

  • 5 无出边，dist 不变

  • dist = [0,5,∞,9,4,3]，S={1,6,5}S=\{1,6,5\}

步骤4：选 2（5），加入 S

  • 2→3：dist[3] = min(∞, 5+7) = 12，prev[3]=2

  • 2→4：dist[4] = min(9, 5+5=10) = 9（不变）

  • dist = [0,5,12,9,4,3]，S={1,6,5,2}S=\{1,6,5,2\}

步骤5：选 4（9），加入 S

  • 4→1：dist[1] = min(0, 9+3=12) = 0（不变）

  • 4→3：dist[3] = min(12, 9+4=13) = 12（不变）

  • 4→5：dist[5] = min(4, 9+7=16) = 4（不变）

  • dist = [0,5,12,9,4,3]，S={1,6,5,2,4}S=\{1,6,5,2,4\}

步骤6：选 3（12），加入 S；3 无出边

  • 结束。dist = [0,5,12,9,4,3]，S={1,6,5,2,4,3}S=\{1,6,5,2,4,3\}

最终最短距离与路径（由 prev 回溯）

  • 到 1：距离 0，路径 1

  • 到 6：距离 3，路径 1 → 6

  • 到 5：距离 4，路径 1 → 6 → 5

  • 到 2：距离 5，路径 1 → 6 → 2

  • 到 4：距离 9，路径 1 → 6 → 4

  • 到 3：距离 12，路径 1 → 6 → 2 → 3