一个既是贪心又是最优的最短路径算法
1
人们总是在做一件事情：
找最短路径
公元前32世纪，苏美尔人在粘土片上制作了城市地图，图上描绘了神庙、公园、城墙、河流。这幅地图是世界上现存最古老的地图。随着人类的发展，地图的形式越来越丰富，但其核心都是一致的，也就是帮助人们找到去某个地方的最短路径。
苏美尔人制作的地图是世界上现存最古老的地图
18世纪初，在普鲁士的格尼斯堡，普瑞格尔河从市中心流过，河中心有两座小岛，岛和两岸之间建筑有七座古桥。
哥尼斯堡的七座桥
当地居民有一项消遣活动，就是试图每座桥恰好走过一遍并回到原出发点。这个问题俗称七桥问题。有很多外地游客慕名而来，跃跃欲试，但从来没人成功过。
于是有人写信给当时著名数学家欧拉，希望他能解决这个问题。欧拉通过简化七桥问题为一个简单图形，证明了这种走法是不存在的。证明过程非常简单，但不经意间他开创了一个新的学科：图论。
时光轮转，20世纪30年代，旅行商问题（Travelling salesman problem， 简称TSP）正式载入史册：
“有一个旅行商人要拜访n个城市，每个城市只能拜访一次，而且最后要回到原来出发的城市。这位商人如何设计拜访顺序，使走过的路径最短？ ”
虽然已经诞生了非常多的启发式算法和精确解法，但一直没有出现能够解决旅行商问题的有效算法。旅行商问题的难度非常大，但是科学家们对它热情不减，希望能找到更加高效的算法。从诞生至今，它一直是优化领域最经常研究的问题之一。
TSP问题历史悠久，最早的描述来自18世纪的骑士环游问题（Knights Moves）
在历史长河中，人们从各个角度致力于寻找最短路径，然而只能做到将路径的表示形式越来越简单，却没有一个机械化算法可以帮助人们快速寻找最短路径。
直到1956年，Dijkstra算法，一个为求最短路径而生的算法，它的诞生改变了这个局面。
2
在咖啡馆诞生的
Dijkstra算法
Dijkstra算法的发明者，叫Edsger Wybe Dijkstra。
Dijkstra是荷兰最早期的程序员，他提出了Go to 有害论（GOTO Statement Considered Harmful），认为只用三种基本控制结构可以写各种程序（即顺序结构、条件结构、循环结构）。这是结构化设计运动的开始，为全世界的程序员指明了方向。
故事要从1952年开始说起。当时Dijkstra刚完成学士学位，参加了剑桥大学开设的一个课程。在他的课程导师，也是著名的英国计算机科学家威尔克斯（Maurice Vincent Wilkes）推荐下，Dijkstra来到了荷兰国家数学研究中心（Mathmetical Centre）。在荷兰数学家阿德里安·范韦恩哈登（Aad van Wijngaarden）领导下开始了编程生涯，参与了新计算机的程序研发，包括ARRA I、ARRA II和ARMAC，开始研发荷兰最早期的第一批计算机。
由于这些计算机还在设计当中，Dijkstra的工作实际上是为这些并不存在的机器写程序，而且只能用纸和笔把程序写出来，验证它们的正确性，和负责硬件的同事确认需要的指令是可以被实现的，并写出计算机的规范说明。因此后来他很习惯于不测试自己写的程序，因为无法测试。
时间来到了1956年，Dijkstra从事编程工作到了第4个年头，此时新计算机ARMAC已经研制完成，为了方便向媒体和公众展示ARMAC的计算能力，Dijkstra需要想出一个可以让不懂数学的媒体和公众理解的问题，来验证这台计算机的实力。Dijkstra思考许久，始终没有一个合适的答案。
就在一个阳光明媚的下午，Dijkstra和未婚妻在一家咖啡馆的阳台上喝咖啡，他习惯性地思考这个问题。
而此时Dijkstra的未婚妻并没有察觉呆呆的Dijkstra，一个劲地跟Dijkstra聊起，准备出门去另一座城市拜访贵族的事情。
Dijkstra突然间灵光一闪，如果让计算机演示如何计算荷兰两个城市间的最短路径，这样问题和答案都容易被人理解。
Dijkstra也不管未婚妻的询问，在沐浴在暖和的阳光下，埋头想着自己的问题，终于在20分钟内想出了一个简洁且高效计算最短路径的方法，也就是我们所熟知的Dijkstra算法。
但当时却没有任何一个期刊关注计算领域，于是Dijkstra没有马上发表。直到3年后的1959年，这个算法才正式发表在Numerische Mathematik创刊号上。
1972年他获得了图灵奖，获奖原因之一，就是因为他提出了Dijkstra算法（图灵奖素有计算机界的诺贝尔奖之称）。
当然，这个算法仅仅是Dijkstra初试身手的处女作。他是一位高产的作家，一生中写了 1300 多篇文章。他用自己姓名的首字母 EWD 给他的文章编号：EWD 1，EWD 2，…EWD 1318。在计算机科学界，这些文章被称为EWD报告。曾在1994 年时有人对约 1000 名计算机科学家进行了问卷调查，选出了 38 篇这个领域最有影响力的论文，其中有5篇来自Dijkstra。
Edsger Wybe Dijkstra
3
Dijkstra算法
是一个既贪心又最优的算法
大名鼎鼎的Dijkstra算法是怎么工作的？
设两个集合，S和U。初始状态下，S只包含源点v，即：S＝{v}，U包含除v外的其他顶点，即：U={其余顶点}。
设dis[u]表示源点v到u的最短距离，若v与U中顶点u有边，则dis[u] = d（v,u）（d（v,u）表示v到u这条边的长度），否则dis[u] = ∞。
第一步，从U中选取一个距离源点v最小的顶点k，即dis[k]最小，把k加入S中，同时在U中剔除k。
第二步，以k为中间点，修改源点v与U中各顶点的距离。若从源点v经过顶点k到顶点u的距离，比原来的dis[u]小（dis[k] + d（k,u） < dis[u]），则更新dis[u]。
第三步，重复第一步和第二步，直至S包含所有顶点，算法结束。
事实上，Dijkstra算法思想非常简洁：
Dijkstra算法对图中的顶点分成两类，一类是已经求出最短路径的顶点集合，用S表示，初始时在S中的只有源点。另一类是其余为未确定最短路径的顶点集合，用U表示。
Dijkstra算法不断在U中挑出与源点距离最短的顶点，加入S中，同时每挑出一个顶点，则利用这个顶点的信息更新U中所有顶点与源点的距离数值。
这种算法有种贪心算法的意味：总是做出在当前看来最好的选择，看似不从整体的角度上考虑，不可能得到最优解。
实际上，Dijkstra算法能够得到最优解，其正确性已被确认，兼具快速和最优的特性。
Dijkstra算法之所以能做到简洁，还有一个重要原因是Dijkstra当时在咖啡馆里没有纸和笔，这强迫他在思考时避免复杂度，尽可能追求简单。
以Dijkstra算法寻找顶点a与顶点b之间的最短路径
4
实际上到处都有
Dijkstra算法的影子
尽管后来有很多新的算法诞生，比如Floyd，SFPA，但是Dijkstra算法因其性能的稳定性，依然在现代得到广泛应用。
互联网时代，网络成为了继水电煤后第四个重要的生存资源。保证网络信号的正常，是一项难度很大的工作。网络信号的传输要经过非常多的中间节点，才能达到目的地。而网络信号的传输速度，取决于当中的路由算法。路由算法的性能必须要好，才能以最快的路径传输信息。
值得注意的是，Dijkstra是现代常用的路由算法。
信号传输经过多个节点，必须使用算法计算最短的传输路径
再试想一下，如果现在若是没有导航软件，估计就连不是节假日都可能堵在路上。特别是遇到高速公路分叉的地方，走错一个都要多耽误半个小时甚至一个小时。
当然，即使有导航软件，现在数据越来越多，可以获知路上哪里发生堵塞、封路、事故，对导航软件的计算要求也越来越高，需要稳定快速的算法来帮助导航软件规划到目的地的最优路径。值得注意的是，从GPS导航诞生开始，Dijkstra算法一直是常用的导航算法。
大到物流路径的规划、大型作业的关键路径计算、小到微型芯片的电路排布、DNA合成都需要计算最短路径，可以说最短路径的计算无处不在，Dijkstra算法则是解决这类问题的热门方案。
5
发现生活中的答案
“生活中从不缺少答案，而是缺少发现答案的眼睛”。
砸到牛顿的苹果，引发了关于万有引力理论的思考。爱因斯坦看到一束光线，沉思如何追一束光，萌发了狭义相对论的框架。Dijkstra在咖啡馆的20分钟思考，成就了Dijkstra算法，一生中最著名的成就之一。
偶然的突发事件，可能带给你新的灵感，而这些新的灵感，也许为你思考已久的问题带来新的思路。看似短暂的瞬间，诞生如此深刻的理解，事实上，这是他们保持对同一问题的长期思考，才能在那一瞬间，得到了自己的答案。
第三十六届CIO班招生
国际CIO认证培训
首席数据官（CDO）认证培训
责编：houlimin
免责声明：本网站（http://www.ciotimes.com/）内容主要来自原创、合作媒体供稿和第三方投稿，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所提供信息的准确性及可靠性，但不保证有关资料的准确性及可靠性，读者在使用前请进一步核实，并对任何自主决定的行为负责。本网站对有关资料所引致的错误、不确或遗漏，概不负任何法律责任。
本网站刊载的所有内容（包括但不仅限文字、图片、LOGO、音频、视频、软件、程序等）版权归原作者所有。任何单位或个人认为本网站中的内容可能涉嫌侵犯其知识产权或存在不实内容时，请及时通知本站，予以删除。
抢沙发
