Dijkstra's algorithm再理解

简介

Dijkstra's algorithm是一个求图中单点到其他所有点最短距离的算法。我在之前的一篇文章里也有过一些讨论。只是那篇文章写得比较仓促，对于该算法的思想和推导理解得也并不深刻。经过一些时间的思考，这里想对该算法的思想做一个进一步的阐述，并对一些和它相关的问题进行比较讨论。

 

算法描述分析

　　对于这个算法来说，它有这么一个前提。在一个连通的图中(可以是有向图或者无向图)，所有的边都有一个对应的权值。我们给定一个起点，需要求基于这个起点到所有其他节点的最短路径。为了解决这个问题，Dijkstra's algorithm的解决步骤如下：

１．设定给定源节点到自身的边权值为0，而到所有其他节点的权值为无穷大。

２．找到距离起点最短的边，因此找到对应的一个节点。这个节点是从起点开始能找到的最近的点。

３．查找是否有到这个最近点的邻接点更短的路径，如果有，则更新这些路径值。

４．重复上述步骤2, 3直到涵盖所有节点。

　　在讨论这个算法的具体正确性以及复杂度之前，我们先以下图为例用上述的步骤来推导一下。 

　　假定图中的红色节点是我们指定的起点。同时我们用一个数组来表示从源节点到其他节点的最短距离。那么，我们按照前面的步骤来说，对于红色节点本身来说，它最短的边就是到它自身的，而且长度为0。这个时候，我们所知的边如下表：

边	权值
0 --> 0	0

　　对应的这个最短长度数组如下：[0, INFINIT, INFINIT, INFINIT, INFINIT, INFINIT, INFINIT]

　　按照前面的过程，我们取权值最小的边。这里最小的就是源节点本身，权值为0。然后，我们要遍历它所有邻接节点来判断是否有更短的路径。在这里，因为最开始初始化为它到其他节点的距离都是无穷大。于是我们相邻两个节点的距离实际上更近，需要更新节点１和２。于是我们得到如下图：

 　　这个时候我们得到的边如下：

边	权值
0 --> 1	4
0 --> 2	10

   　对应的最短路径数组更新为：[0, 4, 10, INFINIT, INFINIT, INFINIT, INFINIT]。我们要注意到一点，每次取我们表里面最短的边之后，就将它从表里面移除。

　　我们再取里面里面最短的边0 -- > 1。 通过节点１再去比较更新它的邻接节点。此时，节点４的值需要被更新。于是有下图：

 　　这个时候，对应的边如下：

边	权值
0 --> 4	25
0 --> 2	10

　　对应的最短路径数组为[0, 4, 10, INFINIT, 25, INFINIT, INFINIT]。我们再去表里面最小权值的边0 --> 2，并比较节点2的所有邻接节点：

 　　对应更新后的表如下：

边	权值
0 --> 4	25
0 --> 3	15
0 --> 5	18

 对应的最短路径数组为[0, 4, 10, 15, 25, 18, INFINIT]。我们再取里面权值最短的边0 --> 3：

 

 　对应的表如下：

边	权值
0 --> 4	20
0 --> 5	18

 　　这一步比较有意思，我们通过节点３的时候又访问到节点４了，之前我们计算出来它的最短路径是２５，而通过节点３得到的最短路径是20。于是我们要更新最小路径数组里对应的值，得到对应的数组为[0, 4, 10, 15, 20, 18, INFINIT]。这个时候，我们再取表里面最短的路径0 --> 5：

 　　在节点５这一步，它又可以遍历到节点４，而按照它的距离加上到节点４的边的权值，这个距离值是30，明显大于前面我们计算出来的20。所以，这里不会更新最短路径数组。这样，我们得到的表如下：

 

边	权值
0 --> 4	20

  　而这里最短路径数组还是和原来的一样：[0, 4, 10, 15, 20, 18, INFINIT]。现在，我们再取最后的边0 --> 4：

　　我们可以得到对应的表如下：

边	权值
0 --> 6	24

  最短路径数组是[0, 4, 10, 15, 20, 18, 24]。我们再取边0 --> 6的时候已经找不到更短的可以更新的节点了。这样，我们就按照这个过程遍历更新了所有的节点。

 

要点 

　　在上述算法的演示过程中，我们用一个表来保存相对于源节点来说它当前能到达的节点的距离。每次取里面最短的那个边，然后再去根据这个边对应的点去检查更新它的邻接节点。而每次在取走最短路径的边并更新到邻接节点距离的值的过程相当于将当前最短路径的这个点给抹去了。

　　在这一步，我们可能会有几个疑问。一个是为什么我们每次要取权值最小的边？而且，我们每次取这个最小权值的边为什么是正确的呢？这是怎么保证的？我们可以以前面示例中的一些过程来说明。以最开始选择０节点的两个邻接节点为例：

　　源节点到１和２的距离分别为４和１０。因为它是从节点0直接相连的，我们取0 --> 1作为当前的最短路径，也就确定了0 --> 1的路径是全局里从节点0到节点１的最短路径，而不会有经过其他点到达节点１而形成更近的节点了。为什么会这样呢？因为我们当前选取的边已经是最小的了，没有比它更小的，所以就算我们选择到其他的边以后也可以连接到节点１，但是其他的边本身已经比边0 -- >1还要大，再加上其他的边连接，只会更大。所以我们就保证了当前取的这个最短边已经是全局最优了。

　　当然，在这里只是针对源节点连接的第一步，对于后续的节点呢？它们是否也符合这样的情况？按照前面的讨论。我们找到一个当前最短路径时，比如0 -- >1，我们就更新１的邻接节点，于是就有了0 -- > 4。这时计算出来的值是25。这个过程我们就可以假想为我们将节点１给消除了，只有一个从节点０直接连接到４而且长度为２５的边。而这个时候，我们再找到的最短路径就已经是0 -- >2了。它本身也相当于我们前面讨论的情况。针对源节点直接连接的点，最短的边也是全局范围内两个点之间最短的路径了。就这样继续不断的推演...

　　因此，对于Dijkstra算法，这里最核心的问题就是我们每次取出来的最短路径就是一个全局最优。我们可以将每次取出最短路径并更新邻接节点的过程看成是加入新的直连节点的过程。这样，我们就更容易理解这个问题了。

 

前提条件 

　　我们前面的推导和讨论其实是基于两个条件的：

1. 图是连通的

2. 所有边的权值是正数。 

　　对于条件１来说，如果图不是连通的，则我们从源节点到很多节点的边权值可以说是无穷大，这个时候就失去比较的意义了。而对于条件２，我们前面的推导里有提到。我们取的当前最小权值边是全局最优的。因为其他比这个边大的边再走若干步的路径到对应的节点会更大。而使得这个距离更大就是因为每一步的权值都是正数，所以我们可以每次放心的把原来的最小节点给删除。而如果出现权值为负数的情况，则还是可能出现从一个权值较大的边最终走到目的节点反而总权值更小。

 

数据结构的选取

　　根据问题的要求，最核心的问题就是我们需要用一个结构来表示图。我们可以用典型的邻接表方式来表示。当然，在这个问题里因为要有每个边之间的权值。我们可以在每个邻接表的元素里保存一系列对应的边。实现的时候可以定义一个专门的WeightedEdge对象。也可以用一个简单的Key value pair来表示。一个表示对应节点的编号，一个表示对应的权值。

　　因为要记录和更新到每个节点的距离值，我们可以用一个数组来记录它们，比如前面示例分析里用的dist[]数组。如果我们要记录最短路径节点，也可以用一个edgeTo[]数组来表示。每个索引位置的元素记录当前节点的前一个节点。

　　当然，还有一个比较重要的地方就是每次遍历更新的边信息。因为希望每次取权值最小的边。从这一点来说看起来我们可以用一个最小堆。但是因为在比较的过程中可能还需要更新表里面的值。所以有的实现是使用一个改进后的indexMinHeap。相当于对最小堆里的元素建了个索引。这种方式相对比较复杂，但是效率比较高。只是目前来说没有现成的类库支持。还有一种办法就是利用一个优先队列结合一个数组来实现。我在之前文章里也有过讨论。

 

和prim算法的差别

　　如果我们仔细看Dijkstra's algorithm会发现它和prim算法很像。因为它们都是根据一个给定的节点，然后扩展到整个图。但是如果仔细去看它们扩展的过程，我们会发现一些细微的差别。Dijkstra算法是计算到给定点最短距离的边，所以每次往外面扩展的时候是取当前最小权值的边再往表里面增加并更新原来的结果。而prim算法是计算到目前涵盖集合里最短的边，所以它不需要是到最开始源节点最短的距离，只要是到当前涵盖的节点集合里元素最近的那个就可以。所以每次它碰到的边不需要做任何加权值的运算而是直接加入到堆里，回头取最小的来判断处理就可以了。

 

总结

　　这篇文章算是对Dijkstra算法的一个思路重新推导。希望能够从一个更加直观的角度来理解整个过程。它本质上是利用了一个从某个节点连接的边里取到的最短的边就一定是全局来说最优的两点路径。所以每次在找到最短路径并更新邻接节点的时候，我们可以将它想象成去掉原来最短路径的点并形成新的更长的边的过程。 

　　Dijkstra's algorithm只适用于边的权值为正数的场景，对于权值为负数的场景，我们应该考虑Bellman-Ford算法。

 

参考材料

Grokking Algorithms

Algorithms