基础-13：两个单源最短路径算法

1 概述

最短路径是图中的常见问题，最典型的应用是：当我们用百度地图或高德地图引导我们去某个地方时，它通常会给出一个相对最短的路径，当然，它也有可能给出一个避开拥堵的时间最短但路径长度不一定最短的路径（这个也可以看成是一个路径间权值可以变化的情况，更复杂了）。本文阐述图中从一个给定的源结点s到所有其它结点最短的路径。

2 相关定义和基本思路

假设图G=(V, E)，其中V为图中的结点，E为图中所有的边，在此，假设图G是有向图，对于G中的边E，存在权重函数w: E->R，图中的权重通常表示一个结点到一个结点之间的代价，如路径长度、耗费时间等，在具体的场景中有具体的意义，本文中暂且认为w是固定不变的（方便处理）,用𝛅(s, v)表示结点s到结点v的最短路径。先看图1:

图1: 图例

如果要求结点s到所有其它结点的路径，该如何处理？

首先，有几个要点必须明白：

• 性质1: 如果从s无法到达结点v，则定义s到v的路径为∞
• 性质2: 如果图G中的边的权值均为确定的正整数，如果v从s可达，则其对短路径是确定的正整数
• 性质3: 如果图G中存在权值和为负的环路，则s到这个环路上的所有结点的最短路径不存在（或者为-∞）
• 性质4: 两个结点之间的存在最短路径< v₀, v₁, v₂, ..., v_k >，则< v₁, v₂, ..., v_k-1 >是v₁到v_k-1的最短路径（注：直观上很好理解，用反证法分析证明）
• 性质5: 最短路径中必然不存在环路（如果所有边的权值为正整数，肯定不可能；如果存在为负值的环路，则必然不存在s到环路中结点的最短路径）

图1中的例子相对简单，𝛅(s, a) = 3，为了求𝛅(s, b) ，因为s到a的路径为<s, a, b>, 所以𝛅(s, b)=3+(-4) = -1，依次类推。如果从s到a存在多条路径，则多条路径中权值最小的路径为最短路径（显然，可以用动态规划求解）。现在的问题是：1）如何比较规整地求出所有的最短路径的权值；2）如何保存最短路径。

对于问题1），根据性质4，要求𝛅(s, v) ，可以先求出𝛅(s, u)，再求w(u, v)，其中(u, v)∈E, 则必然有𝛅(s, v) ≤ 𝛅(s, u) + w(u, v)（分析：可以求出v的所有前驱结点，然后按照这个公式求）。

对于问题2），为了保存所有源结点为s的最短路径，假设其中一条路径为< v₀, v₁, v₂, ..., v_k >，其中v₀=s，则我们需要保存最短路径中各结点间的偏序关系，在此可以构造一个前驱子图G_𝛑=(V_𝛑, E_𝛑)，其中：

• V_𝛑 = {v ∈ V: v.𝛑 ≠NIL} ⋃{s}
• E_𝛑 = {(v.𝛑, v) ∈E: v∈V_𝛑 - {s}},其中v.𝛑表示最短路径中v的前驱（最短路径中，除了s.𝛑 = NIL之外，其它结点的前驱均不为NIL）

显然，G_𝛑是一颗树或森林。如何生成这棵最短路径的树呢？这里需要用到松弛技术，对于每个结点v，假设从s到v的最短距离为v.d，初始时，不知道v.d的值为多少，不妨将其赋值为∞，初始化算法INITIALIZE-SINGLE-SOURCE如图2所示（摘自算法导论）：

图2: 初始化算法

所谓松弛技术就是通过遍历图中的边，最终将v.d收敛到s到v的最短路径，假设存在s到v的路径s->...->u->v,如果有v.d ≥ u.d + w(u, v)，则v.d更新为u.d + w(u, v)，其对应的松弛算法如图3所示（摘自算法导论）为：

图3：松弛算法

3 最短路径算法

有了上面的定义和基础，本节分别介绍Bellman-Ford算法和Dijkstra算法。

3.1 Bellman-Ford算法

Bellman-Ford算法是一种最直接最笨的算法，下面先给出算法，再对算法进行分析说明（分析的时候有些绕，请童鞋们多思考）

图4: Bellman-Ford算法

图4算法中，当图中存在权值为负值的环路时，返回false，否则返回true。算法看上去很简单，但是如何确定它是正确的呢？下面先把《算法导论》中的实例列出来，然后再对算法进行分析。

图5: Bellman-Ford算法图示

接下来分析图4中的Bellman-Ford算法的正确性。第3～4行循环|G.V|-1次，每次循环中都遍历一次所有的边，并且执行松弛操作（第4行），这样即可保证最终可得所有到源结点的最短路径。为什么？

分析：设源结点s出发的最长的最短路径为< v₀, v₁, v₂, ..., v_k >，v₀为s，则k ≤ |G.V|-1，要得到这条路径，考虑遍历的最坏情况，即第一遍遍历是只能确定离s有1跳距离的𝛅(s, v₁)，其它的𝛅值为∞，第二遍遍历只能确定离s有2跳距离的𝛅(s, v₂)，依次类推，即在最坏情况下，循环|G.V|-1次必然能求出所有从源结点s出发的最短路径。思考：再进一步，如果遍历的过程中，不是最坏情况，而是在一次循环中，遍历边的顺序是：先访问距s有1跳距离的边(结点)，然后再遍历距s有2跳距离的边(结点)，依次类推，又会是什么情况呢？需要循环多少次？

在分析出2～4行必然会得到最终的最短路径之后，如果再次遍历一遍所有的边，如果存在v.d > u.d + w(u, v)的情况，则说明必然存在权值为负值的环路。

因此，Bellman-Ford算法是正确的，其复杂度也很好分析，2～4行的复杂度决定了整个算法的复杂度，为O(VE).

显然，在上面的分析中，如果遍历边的顺序合适（即按照拓扑排序边的顺序来），只需要一次循环即可，这样就可降低算法的复杂度降为O(V+E)，其算法为：

图6: 拓扑排序后的最短路径算法

其分析与前面的分析类似，童鞋们可以自己分析

3.2 Dijkstra算法

3.1中的Bellman-Ford算法可以看作是一种暴力算法，有没有更好的算法呢。按照性质4，如果存在最短路径< v₀, v₁, v₂, ..., v_k >，则< v₀, v₁, v₂ >必然是v₀到v₂的最短路径，能否从v₂开始找到这条最短路径呢？Dijkstra算法正是基于这种思想，其基本逻辑为：

假设有一个结点集合S，从源结点s到集合S中的所有的最短路径都已经被找到，然后从V-S中选择最短的路径（这里是估计的𝛅）最小的u，将u加入到集合S，然后对从u出发的所有边进行松弛，直至所有的结点加入大S中。

算法示意如下图7所示：

图7: Dijkstra算法

图7中的算法使用的是贪心算法，即每次加入结点u时，必然有u.d = 𝛅(s, u) （注：这是一个直观可以理解的结论，同样用反证法进行分析，具体分析时关注集合和路径），下图用一个示例说明：

图8: Dijkstra算法过程示例

分析：图7中的算法中，每条边仅被遍历一次，遍历时间为O(E), 第4的while循环会执行|V|次，第5行获取最小值操作时间复杂度为O(V)，因此，整个算法的时间复杂度为O(V² + E)。（当然，根据图是否稀疏，可以对其中的每个步骤进行优化，优化后的时间复杂度取决于第5行所采用的结构）

4 总结

本文对从单源结点s出发的最短路径算法进行了阐述，分别是Bellman-Ford算法和Dijkstra算法，并对两个算法进行了初步的分析，在具体使用时，后者经常使用。图中的算法描述本身都较为简单，但是弄清其原理并对其进行分析才是关键。