问题描述

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

算法思想

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

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

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

算法：

初始化 S=\{1\};

对于 i\in V-S ，计算从 1 到 i 的相对 S 的最短路，长度 \operatorname{dist}[i];

选择 j=\min_{v\in V- S}\operatorname{dist}[v]，将 j 加入 S 并更新 V-S 中顶点的 \operatorname{dist};

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

正确性证明

记

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

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

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

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

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

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

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

保持性：

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

取从 s 到 u 的一条真正最短路，令 y 为该路上第一个不在S的点，x 为其前驱（在 S）。

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

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

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

故我们得到：

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

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

终止：队列空或所有可达点都封口时，所有可达顶点 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

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

• 若用邻接矩阵 + 线性扫描找最小：每轮找最小 O(n)，共 n 轮，外加松弛 O(n^2)，总体 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，逐步把“当前距离最小”的点加入集合 S 并松弛它的出边。记录 dist[] 与前驱 prev[] 。

初始化

• 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\}

步骤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\}

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

• 5 无出边，dist 不变

• dist = [0,5,∞,9,4,3]，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\}

步骤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\}

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

• 结束。dist = [0,5,12,9,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