Dijkstra算法入门

2020-10-31 05:32发布

转载:https://blog.csdn.net/robinvista/article/details/61421034

前言

  最短路径问题(Shortest Path Problem)是一类非常重要的问题,它出现在很多领域,例如车辆导航、路由选择、机器人运动规划、物流等。Dijkstra 算法是一种解决最短路径问题的经典算法,同时也是计算机科学中最有名的算法之一。其方法简洁,但蕴藏的思想却很深刻。通过学习 Dijkstra 算法,既可以掌握分析、解决问题的方法,也可以作为进一步学习其它搜索算法的基础。用一句时髦的话说,Dijkstra 算法——你值得拥有。
  然而,对于缺少一定基础的初学者,要彻底理解 Dijkstra 算法有些困难。笔者发现大多数讲述 Dijkstra 算法的书籍或博客往往不求甚解,只知照本宣科地描述算法的流程,而忽视了算法的由来和内在的逻辑。这样的文章是写给机器看的,而不是给人看的。其后果是,初学者读完后仍然似懂非懂,知其然而不知其所以然。而且初学者在编程实现时又会遇到不少麻烦,让他们举步维艰。本文的目的是帮助初学者尽快入门,为此在表达上力求通俗易懂。文中出现的程序都提供了源代码(Mathematica),方便初学者体验程序的运行过程,并对其解剖研究。

1. 最短路径问题

  最短路径问题的研究范围很大,我们只讨论最简单的情况,即:告诉你一个起点和一个目标点,找到从起点出发到达目标点的最短路径,这又称为单源单目标最短路径问题。一般来说,找到一条连接起点和目标点的路径并不太难,但是想找到最短的路径可就没那么容易了。
  在解决这个问题之前,我们首先需要对它用数学语言进行描述。现实世界总是存在各种约束,比如汽车应该沿着道路行驶、电流必须在电缆上传输、上网产生的数据包只能在路由器之间的网线传递。如果不存在约束,那么最短问题就没有研究价值了——只需要在起点和目标点之间画直线就行了。为了表示现实中的各种约束,同时也为了便于用数学方法进行处理,通常选择数学中的“图”(graph)进行描述(研究“图”的数学学科称为“图论”,图 1(a) 展示了一个“图”的例子)。“图”由两种东西组成:节点(vertex)和 边(edge)。图 1(a) 中的圆点表示节点,黑色线段表示边。我们一般用小写字母表示节点,例如节点a、节点b。每条边的两端是两个节点。因为每条边都唯一对应自己的两个节点,所以可以用两个节点表示一条边。我们用 (a, b) 表示节点 a 与节点 b 之间的那条边。我们将“图”中所有的节点放在一起,组成一个集合,记为 V ;所有的边也放在一起,记为 E。什么是路径(path)呢?一条路径由若干条首尾相接的边组成。我们也可以用一系列相邻的节点表示路径。什么是相邻的节点呢?如果两个节点在同一条边的两端它们就是相邻的,也可以称为“邻居”。一个节点可以有好多个邻居,而且我们假设每个节点至少有一个邻居。既然我们关心路径的长短,就需要有距离的概念。我们定义每条边都对应一个数值,那就是它的长度。我们用 l(a,b) 表示 (a,b) 边的长度。我们只考虑长度为非负数的情况(即 l(a,b)0),因为Dijkstra 算法不适用于负数边长的情况。从此以后,我们进入这个“图”的世界,里面除了节点和边(和它的长度)以外别的什么都没有。你可能会觉得这个小世界太简单、太无聊了。别急,随着我们逐步探索这个小世界,它的丰富多彩将会让你大吃一惊。
  既然寻找最短路径是件很难的事,我们最好先从简单的情况入手。考虑如图 1(a) 所示的例子,这个“图”的节点排列成一个规则网格,所有边的长度都相等,假设长度都是1吧。图中也标出了起点(红色点)和目标点 (绿色点),你能找到它们之间的最短路径吗?


  答案揭晓,最短路径就是图 1(b) 中的黄色线段(为了突出它,我特意画得比普通的边粗一些)。因为两点间直线段最短,起点和目标点之间刚好存在这样组成直线段的边。你可能觉得这太简单了,甚至有智商被侮辱的感觉。事实恰恰相反,这个例子不是太肤浅了,而是太深刻了。我们可以从中找到一条规律,这条规律太重要了,以至于我不得不将它单独放在一段:
  
  规律0:一条直线段上任意两点之间的那部分线段仍然是直线段。
  
  数学家们喜欢干的一件事就是推广——将特殊推广到一般,将简单推广到复杂。比如牛顿的第一个数学发现就是将二项展开式的指数从正整数推广到负数和分数。我们也来试着将前面这条规律推广一下,于是就得到了下一条规律:
  
  规律1:一条最短路径上任意两个节点之间的那部分路径仍然是它们的最短路径。
  
  根据我们的日常经验,规律1似乎是对的,但是我们要从逻辑上证明它的正确性。如果对的不容易发现破绽,那我们就反其道而行之,从错的开始推导。我们假设规律 1 是错的,也就是说:最短路径上存在两个节点,它们之间的那部分路径不是最短路径。图 2(a) 展示的例子就是这种情况,在起点 s 和目标点 t 之间的黄色曲线是它们的最短路径。在这条最短路径上,有两个节点 abab 之间的最短路径(蓝色曲线)比黄色曲线上的那部分更短。从图中可以看到,节点 ab 将黄色曲线分成了三段,即 s-a 段、a-b 段和 b-t 段。三段长度之和就是 st 的最短路径的长度,我们用 Lmin 表示。如果我们用蓝色曲线替换掉黄色曲线上的 a-b 段,如图 2(b) 左侧所示,那么这个重新组合得到的新路径长度显然小于 Lmin 。新的路径比 st 之间的最短路径(黄色曲线)还短,这显然是矛盾的,也就说明规律1是正确的。
  想想看,我们能不能将规律1换种说法:一条最短路径上的任意两个节点之间的最短路径仍然在这条路径上。看起来好像差不多,但其实是不严谨的,因为我们并不知道最短路径是不是唯一的。如果任意两个节点之间的最短路径都只有一条,那么这样说就是对的。但是在有些情况下,两个节点之间的最短路径可能会有不止一条 (它们的长度都是最短的,但经过的节点不同)。所以我们还是应该采用规律1的说法。

2. 搜索算法

2.1 松弛 (relax)

  啊哈!这个小世界开始有意思起来了,我们发现了其中的一条规律。但别高兴的太早,我们怎么利用这条规律呢?如果我给你一条路径,你可以用规律 1 来验证它到底是不是最短的。如果你能在这条路径上找到两个节点,在它们之间有更短的路径,那你可以自信地说我给你的路径肯定不是最短的。注意:规律 1 的重点是“最短路径上”。非最短路径上也可能包含最短的子路径;而两个最短路径拼接到一起得到的路径未必是最短的。规律 1 没有告诉我们怎么计算最短路径。我们试试把规律 1 反过来是什么,这样就得到了另一条规律:
  
  规律2:如果一条路径上的任意两个节点之间的最短路径仍然在这条路径上,那么这条路径就是最短路径。
  
  我们同样不知道规律 2 是不是成立。但经验告诉我们,它很有可能是对的。我们也需要从逻辑上检验规律 2 的正确性。这里我们可以投机取巧,既然规律 2 适用于路径上的任意两个节点,我们不妨选择这条路径的起点和目标点。因为起点和目标点间的最短路径与这条路径重合,显然这条路径就是最短路径。所以规律 2 是正确的。太棒了,因为我们在小世界中又发现了一个新规律。与规律 1 不同的是,规律 2 的提供了一种操作 —— 把一条不是最短的路径变成最短路径的操作:
  1. 随便选择一条连接起点和目标点的路径(不一定最短)。
  2. 在这条路径上任意选择两个节点,搜索它们之间的最短路径。
  3. 如果找到的最短路径不在原路径上,就用最短路径替换掉原来路径的那部分。
  4. 重复第2步和第3步,直到这条路径的长度不再改变。

  我们同样不知道规律 2 是不是成立。但经验告诉我们,它很有可能是对的。我们也需要从逻辑上检验规律 2 的正确性。这里我们可以投机取巧,既然规律 2 适用于路径上的任意两个节点,我们不妨选择这条路径的起点和目标点。因为起点和目标点间的最短路径与这条路径重合,显然这条路径就是最短路径。所以规律 2 是正确的。太棒了,因为我们在小世界中又发现了一个新规律。与规律 1 不同的是,规律 2 的提供了一种操作——把一条不是最短的路径变成最短路径的操作:

  为了帮助大家理解上面几步的含义,下面我用一个简单的例子来解释。假如你由于工作调动,来到了一个新的城市。这个城市的道路构成了一个交通网,如图 3(a) 所示,其中红色点表示你的住所,绿色点表示你的公司。上班第一天,你想找一条开车最快到公司的路。可是你对这个城市的道路不熟悉,所以你只能勉强找一条能到公司的路,如图 3(b) 中所示的粉色路径(好吧,我承认看起来实在是不怎么好)。
  随着时间的流逝,你对这个城市的交通越来越熟悉,附近每条道路的走向和长度逐渐进入你的记忆。虽然你对整个交通网仍然不是非常了解,但对某几段路和它周边道路的印象还是很清楚的,这是因为你走的次数太多了,有时也会走错或者去其它地方,并由此发现了更多的道路。你逐渐发现你最开始找到的那条路并不是最好的。在某条路附近存在更短的路(图4(a) 中虚线内的部分)。于是,你开始超近道,如图 4(b) 所示。以前你走的是经过 (a,b) 边和 (b,c) 边表示的路,现在你知道超近道直接走 (a,c) 边更快。每超一次近道,路径就会短一些,直到你最终找到最短的路径。
  依照上面几步操作我们最终总能找到最短路径。可这是一个好方法吗?看起来似乎不太好。首先我们并不知道运行多少步才能找到短路径。假如你迷路了,向别人问路。那人给你指了一个方向却没告诉你还有多远,你会不会心里没底。其次是第 2 步,很明显第 2 步本身就是一个最短路径问题,它如何求解我们还是不知道。
  虽然上述方法缺少实用价值,但至少它的方向是对的,我们可以从中受到启发。这个方法可以形象的比作被抻长的橡皮筋恢复的过程。如果将路径视为橡皮筋,那么路径的长度就对应橡皮筋中储存的弹性势能。最短路径就是自然状态下(不受外力)的橡皮筋,它不会再缩短了。开始随意确定的路径相当于被抻长的橡皮筋,而以后每一次超近道都可以看成橡皮筋在自身弹力作用下缩短恢复的过程。我们称这一过程为“松弛”(relax),意思就是松开抻长的橡皮筋,让它缩短从而释放掉多余的弹性势能,如图 5 所示。

  松弛现象很容易理解,但是松弛发生的前提条件是什么呢?让我们将注意力集中到路径中的某一条边,如图 6(a) 所示。假设一条路径从起点 s 节点出发,依次经过