5.3 最短路径与 Dijkstra 算法

动机

最短路径问题寻找的是一条路线，而不只是判断两点是否连通。固定源顶点 s 后，我们希望对每个可达顶点 v， 找出从 s 到 v 的最小边权重总和；这就是单源最短路径问题。

第一条被发现的路径未必最短。例如，一条权重为 9 的直接边，后来可能被权重分别为 3 和 2 的两条边取代。 Dijkstra 算法因此先保存暂定估计，通过松弛逐步改进，再按照有证明保证的顺序把顶点确定下来。

适用条件——所有边权重必须非负。 Dijkstra 的贪心确定步骤只有在每条边的权重都至少为零时才正确。 零权重边可以使用；负权重边不可以。图中只要出现一条负权重边，就应改用其他最短路径方法。

这不是可以省略的技术细节。下文会用只有三个顶点、没有负环的例子，直接展示一条负边如何让已确定的答案出错。

定义

设 G=(V,E) 是有向或无向图，源为 s，每条边 (u,v) 的权重满足 w(u,v)\ge 0。一条路径的成本是沿途所有 边权重的总和。用 delta(s,v) 表示从 s 到 v 的真正最短距离；若 v 不可达，距离记作无穷大。

定义

暂定距离与前驱

d[v] 是目前已找到的 s 到 v 路径中最小的成本，所以它是真正最短距离 delta(s,v) 的上界。 pred[v] 记录实现当前 d[v] 的路径上，紧接在 v 之前的顶点。

初始化为

$$d[s]=0,\qquad d[v]=\infty\quad(v\ne s),$$

所有前驱均未定义。找到更优路径时，距离与前驱必须同步更新。

定义

边的松弛

松弛边 (u,v) 时，把旧估计 d[v] 与经过 u 延伸而来的候选值比较：

$$\operatorname{candidate}=d[u]+w(u,v).$$

若候选值严格更小，就设置

$$d[v]\leftarrow d[u]+w(u,v),\qquad \operatorname{pred}[v]\leftarrow u.$$

否则两项都保持不变。

已确定集合 S 保存最短距离已经得到证明的顶点。每一轮从尚未确定的顶点中选出 d 最小者，加入 S，再 松弛它的所有出边。若最小值相同，可以任意打破平局；前驱树可能不同，但最终距离不变。

Dijkstra(G, s):
  对每个顶点 v:
    d[v] = infinity
    pred[v] = undefined
  d[s] = 0
  S = empty set

  当仍有暂定距离有限的未确定顶点:
    u = 暂定距离最小的未确定顶点
    把 u 加入 S
    对每条出边 (u, v)，其中 v 不在 S:
      candidate = d[u] + w(u, v)
      若 candidate 小于 d[v]:
        d[v] = candidate
        pred[v] = u

算法结束后，从目标沿 pred 反向走到 s，再将顺序反转，就可重建路径。仍为无穷大的顶点无法从 s 到达， 也没有可重建的前驱链。

定理 / 命题

定理

有限估计是实际路径成本和上界

在算法的任何时刻，每个有限的 d[v] 都对应一条实际找到的 s 到 v 路径。因此

$$d[v]\ge \delta(s,v).$$

松弛只会使估计下降，而且不会破坏这个上界性质。

定理

非负权重下的安全确定步骤

若所有边权重非负，当 Dijkstra 选出暂定距离最小的未确定顶点 u 时，

$$d[u]=\delta(s,u).$$

所以 u 的距离可以永久确定，之后无须重新打开。

定理

前驱链重建最短路径

算法结束后，从任何可达顶点 v 沿前驱返回 s，所得路径的成本是 d[v]，也就是最短路径成本。 若有多条同成本最短路径，前驱只会记录其中一条。

证明思路

先看上界。初始化的 d[s]=0 代表空路径；之后每个有限估计，都是把一条已由 d[u] 表示的实际路径接上 (u,v) 得到的。因此 d[v] 不可能低于所有可行路径中的最小值。

再证明贪心选择。假设所有已确定顶点的距离都正确，u 是当前暂定距离最小的未确定顶点。取一条 s 到 u 的 最短路径，令 y 是路径上第一个未确定顶点，x 是它之前的已确定顶点。当 x 被确定时，边 (x,y) 已被松弛， 所以结合上界性质可得

$$d[y]=\delta(s,y).$$

从 y 到 u 的剩余边全部非负，因此 delta(s,y)\le delta(s,u)。另一方面，u 是最小暂定值，于是

$$\delta(s,u)\le d[u]\le d[y] =\delta(s,y)\le\delta(s,u).$$

四者只能全部相等，所以 d[u]=delta(s,u)。如果剩余路段包含负边，delta(s,y)\le delta(s,u) 这一步就可能 失效；这正是非负条件不可缺少的原因。

例题详解

例题

一次松弛要同时更新两项数据

假设 d[u]=7、w(u,v)=4，原来 d[v]=14、pred[v]=x。经过 u 的候选成本为

$$7+4=11\lt14.$$

所以更新为 d[v]=11 和 pred[v]=u。若原来 d[v]=10，两者都不改。只改距离而不改前驱，会让最终输出的 数值与重建路径互相矛盾。

例题

从 v0 出发的完整最短路径跟踪

考虑以下有向带权边：

v0->v1(3)、v0->v2(2)、v0->v3(6)、v0->v4(4)、 v1->v3(5)、v1->v5(5)、v2->v4(1)、v4->v3(2)、 v4->v5(4)、v3->v5(1)。

表中括号里的顶点是前驱，破折号表示未定义。确定 v2 后，v1 和 v4 的暂定距离同为 3；以下在这两个同为最小值的顶点中 先选 v1。

阶段	本轮选择	选择后的已确定集合	d[v0]	d[v1]	d[v2]	d[v3]	d[v4]	d[v5]
初始	—	{}	0 (—)	infinity (—)	infinity (—)	infinity (—)	infinity (—)	infinity (—)
松弛 v0 的出边	v0	{v0}	0 (—)	3 (v0)	2 (v0)	6 (v0)	4 (v0)	infinity (—)
松弛 v2 的出边	v2	{v0,v2}	0 (—)	3 (v0)	2 (v0)	6 (v0)	3 (v2)	infinity (—)
松弛 v1 的出边	v1	{v0,v2,v1}	0 (—)	3 (v0)	2 (v0)	6 (v0)	3 (v2)	8 (v1)
松弛 v4 的出边	v4	{v0,v2,v1,v4}	0 (—)	3 (v0)	2 (v0)	5 (v4)	3 (v2)	7 (v4)
松弛 v3 的出边	v3	{v0,v2,v1,v4,v3}	0 (—)	3 (v0)	2 (v0)	5 (v4)	3 (v2)	6 (v3)
在 v5 完成	v5	{v0,v2,v1,v4,v3,v5}	0 (—)	3 (v0)	2 (v0)	5 (v4)	3 (v2)	6 (v3)

最终距离依次为 0,3,2,5,3,6。例如前驱链

$$v_5\leftarrow v_3\leftarrow v_4\leftarrow v_2\leftarrow v_0$$

反转后得到 v0 -> v2 -> v4 -> v3 -> v5，成本为 2+1+2+1=6。v5 的估计先后从无穷大改进到 8、 7、6，清楚说明“已发现”不等于“已确定”。

例题

只有一条负边的最小反例

考虑有向图 s->u(1)、s->v(2)、v->u(-2)。松弛 s 的出边后，d[u]=1 而 d[v]=2，所以 Dijkstra 会先确定 u。然而路径 s->v->u 的成本是 2+(-2)=0，才是真正的最短答案。稍后处理 v 时，算法需要改进一个 已经被声明为最终答案的顶点。这个图没有负环；仅仅一条负边就足以破坏贪心确定论证。

例题

明确说明点权转边权的带权网格

在以下 3 乘 4 点权网格中，求从左上角到右下角的最小成本路径；N 表示不能进入：

	第 1 列	第 2 列	第 3 列	第 4 列
第 1 行	1	2	5	1
第 2 行	4	1	N	N
第 3 行	1	2	1	1

每个可进入方格建立一个顶点。本题只允许向右或向下走一步；目的地越界或为 N 时不建立该边。网格把成本 放在顶点，Dijkstra 则读取边权，所以必须先固定转换规则：

$$w\bigl((i,j),(i',j')\bigr)=M[i'][j'], \qquad d[(1,1)]=M[1][1]=1.$$

也就是每条边收取“进入目标方格”的成本，而初始化另将起点成本计算一次。到右下角的最短路径为

$$(1,1)\to(1,2)\to(2,2)\to(3,2)\to(3,3)\to(3,4),$$

总点权为

$$1+2+1+2+1+1=8.$$

沿第一列向下的另一条路以成本 8 到达 (3,2)，选定路线则以成本 6 到达；两者再走相同后段，总成本分别为 10 和 8。经过 (1,3) 的上方分支不能向下，因为 (2,3) 和 (2,4) 都是障碍。如果把起点初始化为零， 选定路线的边权总和是 7；最后加回起点权重仍得到 8。如果混用两种约定，答案就会出现少算一个方格的错误。

如果用邻接矩阵存图，并线性扫描下一个最小值，时间为 O(V^2)。如果用邻接表配合由二叉堆实现的最小优先队列， 至多 V 次 extract-min 加上至多 E 次优先值更新，时间为

$$O((V+E)\log V),$$

空间为 O(V+E)。在只能向右或向下的 n 乘 m 网格中，V\le nm、E\le 2nm-n-m；障碍只会减少数量， 所以二叉堆实现的时间为 O(nm log(nm))。

实现时，确定顶点的时机同样重要：顶点在作为最小值从优先队列取出时才确定，第一次加入队列只代表找到暂定路径， 之后仍可能被松弛改进。若程序不用 decrease-key，而是每次改进都插入新条目，取出时就要丢弃键值已经不等于 d[v] 的旧条目。若剩余最小键值已经是无穷大，所有未确定顶点均无法从 s 到达，算法可以直接停止，不应虚构前驱。

常见错误

常见错误

有负边仍使用 Dijkstra

只检查有没有负环并不够。标准 Dijkstra 要求每条边都非负，即使图中完全没有负环也一样。

常见错误

把已发现当成已确定

有限估计只代表已经找到一条路；顶点必须成为最小未确定者并被取出，距离才是最终值。完整跟踪例中 v5 的三次改进正好 显示两者的区别。

常见错误

只更新距离而遗漏前驱

每次严格改进都要同步更新 d[v] 和 pred[v]，否则最后显示的成本与重建路径可能来自不同路线。

常见错误

混淆 BFS、Dijkstra 和 MST

BFS 在无权图或所有边成本相同时最小化边数；Dijkstra 最小化非负总权重；MST 最小化连接所有顶点的树的总边权， 并不保证从某个源出发的每条路都最短。

常见错误

没有说明网格成本约定

若数字写在方格中，必须说明成本是在进入还是离开方格时支付，以及是否计算起点。约定未定，路径总值就无法核对。

总结

• d[v] 是暂定上界，pred[v] 记录实现该上界的路线。
• 松弛检查经过 u 延伸能否改进 v，成功时同时更新距离和前驱。
• 所有边非负时，最小未确定估计可以安全成为最终答案；零权边可用，负权边不可用。
• BFS 适合无权最短路径；Dijkstra 处理不相等的非负权重；MST 解决的是另一种总连接成本问题。
• 邻接矩阵配线性选择为 O(V^2)；邻接表配二叉堆为 O((V+E) log V)。

练习

思考检查

一次成功松弛后，哪两项数据必须改变？

分别指出数值记录以及用于重建路径的记录。

1. 已知 d[a]=4、w(a,b)=6、d[b]=13、pred[b]=x，松弛 (a,b)。若原来 d[b]=9，答案又如何？
2. 利用完整跟踪表，重建 v0 到 v3 和 v5 的最短路径，并用边权核对成本。
3. 在 s->u(1)、s->v(2)、v->u(-2) 中，安全确定证明的哪一步失效？
4. 一个无权图用邻接表表示，应选择哪个最短路径算法？时间复杂度是多少？
5. 按照上文网格约定，(3,2) 的估计是多少？比较例中讨论的到达该方格的两条路线。
6. 分别写出 BFS 最短路径、Dijkstra 最短路径和最小生成树目标的一项区别。

答案与解答

解答 · 快速检查答案

成功松弛会把 d[v] 改为更小的候选值，并把 pred[v] 改为产生该候选值的顶点。

解答 · 引导解答

1. 候选值是 4+6=10。从 13 更新为 d[b]=10、pred[b]=a；若旧值为 9，因为 10 并不更小，完全不改。
2. v3 ← v4 ← v2 ← v0 反转为 v0->v2->v4->v3，成本 2+1+2=5。到 v5 再接 v3->v5(1)，总成本为 6。
3. 证明使用了“从 y 到 u 的剩余路段非负”，从而推出 $\delta(s,y)\le\delta(s,u)$。负边 v->u 让这个 不等式失去保证，较大的前段成本反而可以在稍后产生更小的总成本。
4. 使用 BFS；它的队列按边数层次探索，邻接表实现需要 O(V+E) 时间。
5. (3,2) 的估计为 1+2+1+2=6，路径是 (1,1)->(1,2)->(2,2)->(3,2)。 另一条 (1,1)->(2,1)->(3,1)->(3,2) 成本为 1+4+1+2=8，所以松弛保留 6。
6. BFS 在无权图中最小化边数；Dijkstra 从一个源最小化非负路径总权重；MST 则最小化连接全图的生成树总权重。