A.4 最短路径 Dijkstra与A*

1.带权图：边上加了重量

说起来，前面几章我们聊搜索的时候，大多默认每走一步的代价都一样，走一步算一步。可现实里的事往往没那么齐整。今天小张要从杭州去上海，他可以走高速，也可以绕一点走国道，还可以混着来。高速快但绕路，国道直但慢，选哪条不能光看几条边，得把每条边的实际代价都算进去。

这就引出了带权图这个概念。带权图就是在普通的图上面，给每一条边都标上一个数，这个数叫作这条边的权（weight）。权可以代表很多现实含义，可以是距离，可以是时间，可以是花费，也可以是拥堵程度。我们把一条边记作 $(u, v)$，$u$ 和 $v$ 是这条边两端的节点，把这条边的权记作 $w(u, v)$，$w$ 就是 weight 的缩写，代表从 $u$ 走到 $v$ 这一步要付出的代价。

最短路径问题就是要在这张带权图上，找一条从起点到终点、所有边的权加起来最小的路。这条路上各边权之和，叫作这条路径的总权，也叫长度。这类问题在工程里到处都是。地图导航是最直观的例子，打开手机规划一条从家到公司的最快路线，背后跑的就是最短路径算法。网络路由也类似，数据包要从一台机器送到另一台机器，中间要经过若干个路由器，每一段链路有自己的延迟，算法要挑出一条总延迟最小的路。

我们这一章的主角有两个，一个是Dijkstra算法，一个是A*算法。它们都是解决单源最短路径问题的经典做法，单源就是说起点只有一个。各自有各自的特点，我们一个一个来看。

2.Dijkstra：一路挑最近的往外扩

Dijkstra算法的思路说穿了特别朴素。想象小张站在起点，手里拿着一张表格，表格上记着从起点到每一个已知节点的当前最短估计距离。一开始这张表里只有起点自己，距离是 $0$，其他所有节点都先填一个无穷大 $\infty$，$\infty$ 表示暂时还不知道怎么走到那里。然后小张每次都从表里挑一个距离最小、又还没真正确定下来的节点，把它正式确定下来，再顺着它的边去看看能不能把邻居的距离更新得更短。就这么一步一步往外扩，直到所有能到的点都被确定下来。

我们拿一张小图手动走一遍，这样最清楚。设这张图有五个节点，分别是 $A$、$B$、$C$、$D$、$E$，起点是 $A$。边和权这样安排：从 $A$ 到 $B$ 权为 $6$，从 $A$ 到 $D$ 权为 $1$，从 $D$ 到 $B$ 权为 $2$，从 $D$ 到 $E$ 权为 $5$，从 $B$ 到 $C$ 权为 $5$，从 $B$ 到 $E$ 权为 $2$，从 $E$ 到 $C$ 权为 $1$。

一开始距离表是这样：$A$ 是 $0$，$B$、$C$、$D$、$E$ 全是 $\infty$。

第一步，挑出当前距离最小又没确定的节点，显然是 $A$，距离 $0$。把它确定下来。然后顺着 $A$ 的两条边往外看。从 $A$ 到 $B$ 这条边权是 $6$，走到 $B$ 的距离就是 $0+6=6$，比 $B$ 原来的 $\infty$ 小，把 $B$ 更新成 $6$。从 $A$ 到 $D$ 这条边权是 $1$，走到 $D$ 的距离是 $0+1=1$，也比 $\infty$ 小，把 $D$ 更新成 $1$。

第二步，从未确定的节点里挑距离最小的。现在 $D$ 是 $1$，$B$ 是 $6$，$C$ 和 $E$ 还是 $\infty$，挑 $D$。把 $D$ 确定下来。顺着 $D$ 的两条边看。从 $D$ 到 $B$ 权 $2$，经过 $D$ 走到 $B$ 的距离是 $1+2=3$，比 $B$ 现在的 $6$ 小，把 $B$ 更新成 $3$。从 $D$ 到 $E$ 权 $5$，经过 $D$ 走到 $E$ 的距离是 $1+5=6$，比 $\infty$ 小，把 $E$ 更新成 $6$。

第三步，再挑最小。现在 $B$ 是 $3$，$E$ 是 $6$，$C$ 还是 $\infty$，挑 $B$。把 $B$ 确定下来。从 $B$ 到 $C$ 权 $5$，经过 $B$ 走到 $C$ 的距离是 $3+5=8$，把 $C$ 更新成 $8$。从 $B$ 到 $E$ 权 $2$，经过 $B$ 走到 $E$ 的距离是 $3+2=5$，比 $E$ 现在的 $6$ 小，把 $E$ 更新成 $5$。这里有个细节值得留意，$E$ 的距离在过程中被更新了两次，先是 $6$，后来又缩成 $5$，这正是距离表不断逼近真实最短值的过程。

第四步，再挑最小。现在 $E$ 是 $5$，$C$ 是 $8$，挑 $E$。把 $E$ 确定下来。从 $E$ 到 $C$ 权 $1$，经过 $E$ 走到 $C$ 的距离是 $5+1=6$，比 $C$ 现在的 $8$ 小，把 $C$ 更新成 $6$。

最后一步，把 $C$ 确定下来，距离 $6$。到此所有节点都确定完毕。我们从 $A$ 到 $C$ 的最短路径是 $A \to D \to B \to E \to C$，总权 $6$。这比一开始直觉上那条 $A \to B \to C$（总权 $11$）要短不少。说明一个道理，最短路径常常不是边数最少的那条，绕几个中转点反而更省。

这里要特别强调一个前提，Dijkstra算法要求图上所有边的权都不能是负数。为什么这么要求呢，因为算法每次都是贪心地挑当前距离最小的点来确定，认准了它以后不会再变短。一旦有负权边存在，后面可能突然蹦出一条更短的回头路，把已经确定好的结果推翻，整套逻辑就乱了。所以遇到带负权的图，Dijkstra不能用，得换别的方法。

接下来讲复杂度。朴素实现里，每一步都要在所有未确定节点里挑一个最小的，挑一次扫一遍，效率不高。工程上的标准做法是用优先队列（priority queue，也叫最小堆）来加速，这样每次挑最小的只需要对数时间。设图里一共有 $V$ 个节点和 $E$ 条边，$V$ 是节点数，$E$ 是边数，那么总的时间复杂度约为 $O((V+E)\log V)$。这个效率对绝大多数稀疏图都相当够用，所以工程里Dijkstra是最常用的单源最短路径算法之一。我记得之前看过一本讲算法史的书，里头说Dijkstra本人最初给的实现其实是 $O(V^2)$ 的，后来配上优先队列才变成现在这个样子，可见一个好数据结构能把算法带得多远。

3.A*：加一个直觉，朝目标走

Dijkstra有一个小毛病。它挑下一个要扩展的节点时，只看从起点出发已经走了多远，完全不管目标在哪个方向。这就好比你站在一个陌生的十字路口问路，别人只告诉你已经走了几公里，却一句也不提目的地在左边还是右边，你自然容易绕远路。小明有次跟我抱怨，说地图软件偶尔会把他导进一条莫名其妙的小路绕一大圈，大概就是纯距离逻辑没把方向感揉进去。

A*算法就是来补上这一块的。它在Dijkstra的基础上加了一个启发函数 $h(n)$，$n$ 是图里的某个节点，$h(n)$ 是对从 $n$ 到终点的距离的一个估计值。这个估计可以来自直线距离，可以来自某种经验公式，只要它能反映大概的方向就行。

A*用一个综合指标来决定先扩展哪个节点，记作 $f(n)$，定义是：

$$f(n) = g(n) + h(n)$$

这里 $g(n)$ 是从起点实际走到 $n$ 已经花掉的代价（也就是Dijkstra里那张距离表上的值），$h(n)$ 是对 $n$ 到终点还剩多远的估计，$f(n)$ 是两者之和，可以理解成从起点经过 $n$ 一路到终点的预估总代价。算法每次挑 $f(n)$ 最小的节点优先扩展，这样一来，就既照顾已经走掉的路，又朝着终点的方向偏过去。

A要保证找到的是真正的最短路径，有一个关键条件，就是 $h(n)$ 必须可采纳。可采纳的意思是，$h(n)$ 永远不能高估从 $n$ 到终点的真实最短距离，它最多等于真实值，更多时候应该比真实值小一些。这么要求的原因也好理解，只有估计值不偏大，算法才不会因为某个看起来很近、其实绕远的节点，把真正最优的那条路错过。两个极端能帮我们看清这件事。如果 $h(n)$ 恒为 $0$，那么 $f(n)=g(n)$，A就退化成了Dijkstra，保证最优但慢。如果 $h(n)$ 恰好等于真实最短距离，A*就直直地沿着最优路径走下去，几乎不绕弯。实际工程里，我们尽量挑一个既不高估、又贴近真实值的 $h(n)$，在最优和速度之间取一个划算的折中。

A最常见的应用场景之一，是游戏里的自动寻路。我之前玩过一款即时战略游戏，地图上一格一格的，有山有水有障碍，点一下让单位从这头走到那头，背后跑的就是A。在那类网格地图上，$h(n)$ 通常取直线距离，常用的有两种，一种叫曼哈顿距离，就是横向格数差加纵向格数差之和，适合只能上下左右走的世界。另一种叫欧几里得距离，就是两点之间的几何直线距离，适合可以任意方向走的世界。选哪个要看地图本身允不允许斜着走。

和Dijkstra相比，A在目标明确的情况下扩展的节点要少很多，因为它有方向感。代价是要花心思设计 $h(n)$，$h$ 设计得糙，效果可能还不如直接跑Dijkstra。说穿了，A的精髓就是把对目标的预感，形式化成一个能算的函数，再把它揉进搜索的过程里。

4.负权和全源：Bellman-Ford和Floyd

Dijkstra和A*都怕负权，可工程里确实会碰到负权。举个不那么直观的例子，金融里有人研究套利检测，把各种货币之间的汇率建成一张图，某种货币兑换另一种货币的汇率取对数后取负号当作边权，一旦图里出现一条总权为负的环，就说明存在无风险套利的机会。这类图天然带负权甚至负环，Dijkstra直接没法用。

这时候要请出Bellman-Ford算法。它的思路比Dijkstra还要直白，就是对每一条边都反复做松弛操作。松弛（relaxation）说的是这样一件事：看一条边 $(u, v)$，要是发现 $u$ 的当前最短距离加上 $w(u, v)$ 比 $v$ 的当前最短距离还小，就把 $v$ 更新成这个更小的值。Bellman-Ford就把所有边的松弛操作重复 $V-1$ 轮。为什么是 $V-1$ 轮呢，因为一条最短路径最多经过 $V-1$ 条边，再多就要重复走节点，意味着进了环，而除了负环之外的最短路径不会绕着环走。这么一轮一轮松弛下来，结果自然就收敛了。Bellman-Ford还有一个附带的好处，它能检测出图里有没有负环，只要在 $V-1$ 轮之后再扫一遍所有边，发现还能继续松弛，就说明存在负环。它的复杂度是 $O(VE)$，比Dijkstra慢一些，但能处理负权，这是它的看家本领。

还有一种完全不同的需求，叫全源最短路径，就是求出图里任意两个节点之间的最短距离。一个直观的做法是，对每个节点都跑一遍Dijkstra，一共跑 $V$ 次。但有更优雅的算法，叫Floyd算法（也叫Floyd-Warshall）。它的核心是一个动态规划，思路很妙，依次考虑每个节点作为中间点，看看任意两点之间经过这个中间点会不会更短。设 $D_{ij}$ 表示节点 $i$ 到节点 $j$ 的当前最短距离，对每个中间点 $k$，做这样一次更新：

$$D_{ij} = \min(D_{ij},\ D_{ik} + D_{kj})$$

这里 $\min$ 表示取括号里两个数中的较小值，$D_{ik}$ 是 $i$ 到 $k$ 的当前最短距离，$D_{kj}$ 是 $k$ 到 $j$ 的当前最短距离。这条式子的意思是，从 $i$ 到 $j$ 的最短距离，要么是不经过 $k$ 的那种走法，要么是先到 $k$ 再从 $k$ 到 $j$ 的那种走法，两者取小。把所有 $k$ 都轮一遍，$D_{ij}$ 就收敛到了真正的全源最短距离。Floyd的复杂度是 $O(V^3)$，节点一多就吃不消，但它的代码极短，三重循环就搞定，特别适合节点数不多（比如几百个以内）又需要频繁查任意两点距离的场景。

说起来，这几种算法各有各的位置。Dijkstra适合大多数边权非负的稀疏图，Bellman-Ford是有负权时的兜底，Floyd是节点不多又要全源查询时的首选。

5.一个共同的骨架：状态空间里的搜索

写到这里不妨往回看一眼。无论是Dijkstra一层层往外扩，还是A*顺着启发函数朝目标走，它们背后其实是同一套东西，就是在某种结构里搜索一条从起点到目标的、代价最小的路。

这套思想到后面会反复出现。强化学习里智能体在一个状态空间里摸索，要从当前状态走到一个回报最高的状态，本质上就是在一个带权图上找路，只不过这个图的规模大得惊人、边的权要靠试错来一点点估。规划问题里，机器人要从当前位置走到目标位置，中间要避开障碍、要省电省时，状态空间搜索的那一套做法同样派得上用场。我之前翻过一本讲人工智能史的书，里头提到上世纪六七十年代那些做机器定理证明、做下棋程序的人，最早琢磨的就是怎么在一个巨大的可能性空间里高效地找路，今天的最短路径算法，可以说是那批思想最干净的一个结晶。

说穿了，最短路径算法是状态空间搜索的一个最成熟的样板，把它吃透了，后面遇到更复杂的搜索问题，心里就有一根主心骨。

练习

Q1. Dijkstra算法为什么要求所有边的权都不能是负数？用优先队列实现的时间复杂度是多少？

因为算法每次贪心地挑当前距离最小的点来确定，认准了它以后不会再变短。一旦有负权边，后面可能突然蹦出一条更短的回头路把已经确定的结果推翻，整套逻辑就乱了，所以带负权的图Dijkstra不能用（要换Bellman-Ford）。用优先队列（最小堆）实现时，每次挑最小的只要对数时间，总时间复杂度约为 $O((V+E)\log V)$，对绝大多数稀疏图都够用。

Q2. A*算法的综合指标 $f(n)=g(n)+h(n)$ 各项含义是什么？$h(n)$ 要满足什么条件才能保证找到最短路径？

$g(n)$ 是从起点实际走到 $n$ 已经花掉的代价（就是Dijkstra距离表上的值），$h(n)$ 是对 $n$ 到终点还剩多远的估计（启发函数，可来自直线距离或经验公式），$f(n)$ 是从起点经 $n$ 到终点的预估总代价，算法每次挑 $f(n)$ 最小的节点优先扩展。$h(n)$ 要满足"可采纳"——永远不能高估从 $n$ 到终点的真实最短距离，最多等于真实值、更多时候比真实值小，只有估计不偏大才不会错过最优解。两个极端：$h(n)\equiv0$ 时A*退化成Dijkstra（保证最优但慢）；$h(n)$ 恰等于真实距离时直直沿最优路径走。

Q3. 易错点：Floyd算法和"对每个节点跑一遍Dijkstra"都是求全源最短路径，它们可以随便替换吗？

不能完全随便换。Floyd是动态规划，三重循环、复杂度 $O(V^3)$、代码极短，适合节点数不多（几百个以内）又需要频繁查任意两点距离的场景；但它对所有边权也有非负要求时才稳（实际Floyd能处理部分负权但不能有负环）。"对每个节点跑Dijkstra"是跑 $V$ 次Dijkstra，配优先队列总复杂度 $O(VE\log V)$，对稀疏图比Floyd划算，但Dijkstra本身怕负权。所以选哪个要看图的疏密、节点数大小、有没有负权——节点少要全源查询选Floyd，稀疏大图选多次Dijkstra，有负权选Bellman-Ford。