最短路径毕业论文

安庆师范学院数学与计算数学学院2013届毕业论文第1页共9页最短路算法的比较与应用作者：胡义棚指导老师：丁超摘要：本文较详尽地介绍了最短路算法相关的基本概念，给出了Dijkstra算法、Floyd算法、SPFA算法等常用算法及其核心思想，并对各种最短算法做了多角度的比较，阐述了各种算法的应用范围，并对其在运输网络、舰船通道路线设计、工业生产中的应用做出了举例说明，侧重于模型的建立、思考和证明的过程，最后作出总结.关键词：最短路算法Dijkstra算法Floyd算法SPFA算法一、引言最短路算法是图论中的核心问题之一，他是许多更深层次算法的基础，同时，该问题有着大量的生产实际的背景.很多问题从表面上看与最短问题没有什么关系.却也可以归结为最短路问题，本文通过收集整理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题，工程问题，及实际生活问题中的应用，为企业和个人提供方便的选择方法.二、最短路2.1最短路的定义对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权)0(ijw的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路.后来海斯在Dijkstra算法的基础之上提出了海斯算法.但这两种算法都不能解决含有负权的图的最短路问题.因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题.但在现实生活中,我们所遇到的问题大都不含负权,所以我们在)0(ijw的情况下选择Dijkstra算法定义1若图),(EVGG中各边e都赋有一个实数)(eW,称为边e的权,则称这种图为赋权图,记为),,(WEVGG.定义2若图),(EVGG是赋权图且)(,0)(GEeeW,若u是iv到jv的路)(uW的权,则称)(uW为u的长,长最小的iV到jV的路)(uW称为最短路.若要找出从iv到nv的通路u,使全长最短,即minijeuWuWe.2.2各类最短路算法的介绍2.2.1Floyd算法Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法.该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名.其核心思路是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵.即从图的带权邻接矩阵2)],([njiaA开始，递归地进行n次更新，即由矩阵AD)0(，按一个公式，构造出矩阵)1(D；又用同样地公式由)1(D构造出)2(D；……；最后又用同样的公式由)1(D构造出矩阵)(nD.矩阵)(nD的i行j列元素便是i号顶点到j号顶点的最短路径长度，称)(nD为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径.下面介绍其算法过程：)1从任意一条单边路径开始.所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大;安庆师范学院数学与计算数学学院2013届毕业论文第2页共9页)2对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短.如果是更新它;)3把图用邻接距阵G表示出来，如果从iV到jV有路可达，则djiG],[,d表示该路的长度；否则],[jiG为无穷大;)4定义一个距阵D用来记录所插入点的信息，],[jiD表示从iV到jV需要经过的点，初始化jjiD],[;)5把各个顶点插入图中，比较插点后的距离与原来的距离，]),[min(],[jiGjiG，],[],[jkGkiG，如果],[jiG的值变小，则kjiD],[;)6在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息.2.2.2Dijkstra算法Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等.Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式.注意该算法要求图1中不存在负权边.下面介绍其算法过程：首先，引进一个辅助向量，它的每个分量D表示当前所找到的从始点V到每个终点iV的最短路径的长度.如2]3[D表示从始点v到终点3的路径相对最小长度为2.这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度.它的初始状态为：若从V到iV有弧，则D为弧上的权值；否则置D为∞.显然，长度为}|{][VVDMinjDi的路径就是从V出发的长度最短的一条最短路径.此路径为),(jVV.那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是kV，则可想而知，这条路径或者是),(kVV，或者是),,(kjVVV.它的长度或者是从v到vk的弧上的权值，或者是][jD和从jV到kV的弧上的权值之和.一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧),(XV，或者是中间只经过S中的顶点而最后到达顶点X的路径.因此，下一条长度次短的最短路径的长度必是}|{][VVDMinjDi其中，D或者是弧),(iVV上的权值，或者是)]([SVkDk和弧),(ikVV上的权值之和.迪杰斯特拉算法描述如下：1）arcs表示弧上的权值.若不存在，则置arcs为.S为已找到从v出发的最短路径的终点的集合，初始状态为空集.那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为LocatearcsD[)](),,(2vviVGVexi,使得}|{][SVDMinjDi修改从V出发到集合SV上任一顶点kV可达的最短路径长度.6123459511151071481216安庆师范学院数学与计算数学学院2013届毕业论文第3页共9页2.2.3Bellman-Ford算法Dijkstra算法中不允许边的权是负权，如果遇到负权，则可以采用Bellman-Ford算法.Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题.对于给定的带权（有向或无向）图),(EVG，其源点为S，加权函数W是边集E的映射.对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点S可达的负权回路.若不存在这样的回路，算法将给出从源点S到图G的任意顶点V的最短路径][VD.下面介绍其算法过程：)1初始化：将除源点外的所有顶点的最短距离估计值0][,][SDVD)2迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点V的最短距离估计值逐步逼近其最短距离（运行1V次）；)3检验负权回路：判断边集E中的每一条边的两个端点是否收敛.如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在][vd中.2.2.4SPFA算法求单源最短路的SPFA算法的全称是：ShortestPathFasterAlgorithm.SPFA算法由西南交通大学段凡丁于1994年发表.很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了.下面介绍其原理与算法过程：我们约定有向加权图G不存在负权回路，即最短路径一定存在.当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路.我们用数组D记录每个结点的最短路径估计值，而且用邻接表来存储图G.我们采取的方法是松弛：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点U，并且用U点当前的最短路径估计值对离开U点所指向的结点V进行松弛操作，如果V点的最短路径估计值有所调整，且V点不在当前的队列中，就将V点放入队尾.这样不断从队列中取出结点来进行松弛操作，直至队列空为止.每次将点放入队尾，都是经过松弛操作达到的.换言之，每次的优化将会有某个点V的最短路径估计值][VD变小.所以算法的执行会使D越来越小.由于我们假定图中不存在负权回路，所以每个结点都有最短路径值.因此，算法不会无限执行下去，随着D值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值.所以只要最短路径存在，上述SPFA算法必定能求出最小值.2.3最短算法的比较2.3.1Floyd算法求多源、无负权边的最短路.用矩阵记录图.时效性较差，时间复杂度)(3VO.Floyd-Warshall算法（Floyd-Warshallalgorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题.Floyd-Warshall算法的时间复杂度为)(3NO空间复杂度为)(3NOFloyd-Warshall的原理是动态规划：设kjDi,,为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度.若最短路径经过点k，则kjDi,,kjDi,,1kjDi,,若最短路径不经过点k，则kjDi,,kjDi,,安庆师范学院数学与计算数学学院2013届毕业论文第4页共9页因此，kjDi,,)1,,,1,,1,,min(kjDikjDkkkDiDijkstra求单源、无负权的最短路.时效性较好，时间复杂度为)(2EVO.源点可达的话，)lg()lglg(vEOVEVVO.当是稀疏图的情况时，此时2VE/Vlg，所以算法的时间复杂度可为)(2VO.若是斐波那契堆作优先队列的话，算法时间复杂度，则为)lg(EVVO.Bellman-Ford求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度)(VEO.Bellman-Ford算法是求解单源最短路径问题的一种算法.单源点的最短路径问题是指：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径.与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数.设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负.那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去.如果不处理这个负环路，程序就会永远运行下去.而Bellman-Ford算法具有分辨这种负环路的能力.SPFA是Bellman-Ford的队列优化，时效性相对好，时间复杂度)(keO.)(vk与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径.所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数.SPFA算法可以用于存在负数边权的图，这与dijkstra算法是不同的.与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别.在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为)(eO另一方面，存在这样的例子，使得每一个节点都被入队)1(V次，此时算法退化为Bellman-ford算法，其时间复杂度为)(VEO.SPFA算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好.但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的使用堆优化的版本.通常的SPFA算法在一类网格图中的表现不尽如人意.完.2.4最短路算法的应用在运输网络中的应用设6个城市126,,,vvv之间的一个公路网(图1)每条公路为图中的边,边上的权数表示该段公路的长度(单位:百公里),