算法导论随笔(八)：图的最短路径问题与Dijkstra算法

在上一篇文章中，我介绍了图(Graph)的概念。这篇文章和未来几篇文章中，我主要讨论关于图的一些经典问题和解决这些问题的经典算法。首先是图的最短路径问题。

1. 图的最短路径(Shortest Path)问题

首先来讨论图的最短路径问题。举一个例子，我们可以把中国的地图看做一个图，把每一个城市看做图中的一个顶点，把相邻城市的高速公路当做一条边。那么，如果我想从北京出发去上海，要经过哪些城市才能使得走过的距离最短呢？
这就是图的最短路径问题。给定一个图，图中每一条边都有一个权重(weight)。比如上面的例子中每两个城市之间的高速公路是一条边，公路长度是权重。最短路径问题就是求有向图中给定两个顶点之间的一条路径，使得该条路径上所有边的权重的和最小。例如下面的这个图，图中红色的三条边和四个蓝底的顶点所组成的路径即是PVD到HNL的最短路径。也就是说，在图中，从PVD道HNL的所有路径中，我们找不到任何一条其他路径比这条路径还要“短”（也就是边的权重之和最小）。

2. 最短路径的特性

若一条路径是一个图中两个顶点之间的最短路径，那么该路径有如下特性：

1. 该路径的子路径也是一条最短路径。比如上图中的最短路径的一条子路径是从PVD到ORD到LAX。这条子路径也是从PVD到LAX的最短路径。
2. 图中存在这样一棵树，该树用来表示从该路径的出发点到图中所有其他顶点的最短路径，而且这条最短路径是树的一个树枝(其实该树就是这个图的最小生成树，这个概念我会在以后介绍)。

下面的图中就是这棵树的例子。该树的根节点(root)为PVD。

3. 用Dijkstra算法求解最短路径问题

对于解决最短路径问题的解法，我们最先想到的，也是最直观的解法，可能就是求出图中两个点之间的每一条路径，然后计算每一条路径的总权重，总权重最小的那条路径就是最短路径。但是，即便是在不允许环路(即重复经过某个顶点)的情况下，也可以看出，我们需要检查大量的路径，而其中很多路径根本不值得检查。比如从北京到上海，经过*的路径显然不是最短路径。

Dijkstra算法通过贪心策略解决了这个问题。(还记得贪心策略吗？在算法导论随笔(六)：贪心算法Greedy algorithm与分数背包问题(附Python实现源码)中，忘了的同学可以去复习一下)。贪心策略的基本思想就是在每一步中都选择目前收益最大的操作。这也符合了最短路径的第一条特性：一个最短路径的子路径仍然是最短路径。Dijkstra算法有一个前提条件，即图中的每一条边的权重都不能是负值。因此，在讨论Dijkstra算法之前，我们先规定，对于接下来要讨论的图
$G = (V, E)$G=(V,E)
我们有
${\forall} e = (u, v) \in E, w(e) \ge 0$∀e=(u,v)∈E,w(e)≥0
即：图中任意一条边e，其权重w(e)大于或等于0。

注意： 最短路径有几个变体，我们接下来要讨论的是单源最短路径问题，也就是说，给定一个图G = (V, E)，我们希望从给定源节点(也就是出发点)
$s \in V$s∈V
到每个节点
$v \in V$v∈V
的最短路径。也就是说，求出一个节点s到图中其他所有节点的最短路径（当然，求出了一个顶点到所有其他顶点的最短路径，那么自然也求出了一个顶点到一个特定顶点的最短路径）。

接下来我们来看Dijkstra算法的伪代码。

该算法的输入为一个不含负权值边的无向图G和G中的一个顶点v。
该算法的输出为，对于图中每一个节点u，给出表示v到u的最短距离D[u]。

4. Dijkstra算法解析

现在来分析一下上面的伪代码。
首先把D[v]设置为0，对于其他每一个节点v，设置D[v]为无穷大。
接下来初始化一个优先级队列，这个队列中包含所有顶点，包括v。该队列以顶点的D值从小到大排列。也就是说，D值为0的顶点v处于该队列的队尾(也就是说，若从队列中弹出第一个顶点，则该顶点为v)。
接下来是重点：
当优先级队列不为空的时候，首先弹出一个顶点。这个顶点一定是当前优先级队列中D值最小的点。取名为u。
接下来，得到u在图中，并且仍在队列中的所有邻接点(不知道邻接点的概念的话，可以看这篇文章)；对于每个邻接点z，做如下处理：
如果D[u]与w(u, z)的和小于D[z]的值，则把D[u]与w(u, z)的值赋给D[z]。这里w(u, z)指的是从u到z这条边的权重值。此时由于D[z]的值已经改变，所以z在优先级队列中的位置也要改变。
若D[u]与w(u, z)的和不小于D[z]的值，则不作任何处理。
循环上述操作直到优先级队列中所有顶点都被取出，即优先级队列为空。此时每一个顶点u的D值即是顶点v到u的最短距离。

下面举一个例子来说明这个算法是如何操作的。假如我们有一个下图中的图，想求顶点A到其他顶点的最小距离。每条边的权重标在该条边上。

首先第一步是把点A的D值设置为0，并且把其他点的D值设置为无穷大。然后把它们插入一个优先级队列中。接着由于A的D值最小，因此从队列中取出点A。并且得到它在图中的三个邻接点，B，C和D。
接下来对于这三个点，比较D[u]+w(u, z)与D[z]的值。对于B，C和D来说，因为它们的D值都为无穷大，因此D[z]一定比D[u]+w(u, z)大。所以更新D[B]，D[C]和D[D]的值。如下图。虚线内所示为已经从队列中弹出的顶点

例如，图中D[B]被更新为D[A] + w(A, B)，也就是0 + 8 = 8。D[C]和D[D]的值被更新为2和4。
在这一步操作之后，优先级队列变为：
{C: 2, D: 4, B: 8, E: 无穷大, F: 无穷大}。
C成为队列中的新队尾，因此下一步从队列中弹出C。由于A已经不在队列中，因此得到邻接点B，D，E和F。根据算法，更新各个顶点的D值，如下图。

在这一步操作之后，优先级队列变为：
{D: 3, E: 5, B: 8, F: 11}。
因此下一步弹出D。由于A和C都已经不在队列中，因此更新F的D值，如下图：

在这一步操作之后，优先级队列变为：
{E: 5, B: 8, F: 8}。
因此下一步弹出E。由于C已经不在队列中，因此更新B的D值，如下图：

在这一步操作之后，优先级队列变为：
{B: 7, F: 8}。
因此下一步弹出B。由于A，C和E均已经不在队列中，因此不作任何操作。结果如下图。

在这一步操作之后，优先级队列变为
{F: 8}。
因此下一步弹出F。由于C和D均已经不在队列中，因此不作任何操作。优先级队列变为空。算法结束。
最终的结果如下图：

每个顶点的D值为
D[A] = 0
D[B] = 7
D[C] = 2
D[D] = 3
D[E] = 5
D[F] = 8
每个顶点的D值代表了从A出发到该点的最短距离。图中标红色的边为最短路径的边。例如，从A到F的最短路径为(A, C), (C, D), (D, F)。三条边的权重和为2 + 1 + 5 = 8。

算法的复杂度取决于优先级队列是如何实现的。如果用二叉堆来实现最小优先队列，则算法复杂度为O((V + E)logV)，其中V表示图中顶点数量，E表示图中边的数量。
算法的复杂度分析如下。
每次向优先级队列中插入一个值为O(1)。插入V个值，则为O(V)。

对于由二叉堆实现的优先级队列，从队列中每次取一个值为O(logV)，所以全取出的话需要O(VlogV)。

最关键的是更新D值的操作。我们每次把一个顶点的邻接点拿出来计算D值。一个邻接点是用一条边与当前顶点相连。所以，计算多少个点的D值取决于图中有多少边。计算邻接点的D值后要修改该点在队列中的key值，由于队列由二叉堆实现，该操作耗费O(logV)。这个操作的数量取决于边的数量，因此，修改所有顶点的邻接点D值的操作耗费O(ElogV)。
因此，该算法的复杂度为
$T(n) = O(V) + O(VlogV) + O(ElogV) = O(V + (V + E)logV) = O((V + E)logV)$T(n)=O(V)+O(VlogV)+O(ElogV)=O(V+(V+E)logV)=O((V+E)logV)

5.写在最后

Dijkstra算法是一个经典算法，该算法计算出一个图中给定顶点到其他所有顶点的最短路径。该算法使用了贪婪策略，算法的中心思想就是，如果求两个不相临的点之间的最短路径，那么就先保证它们的路径之间的所有子路径都是最短路径（也就是最佳选择）。