最短路算法的比较与应用

1、最短路算法的比较与应用摘要：本文较详尽地介绍了最短路算法相关的基本槪念，给出了 Dijkstra K法、Floyd算法、SPFA 算法等常用算法及其核心思想，并对各种最短算法做了多角度的比较，阐述了各种算法的应用 范国，并对其在运输网络、舰船通道路线设计、工业生产中的应用做出了举例说明，側垂于模 型的建立、思考和证明的过程，最E作出总结.关键词：灵短路算法Dijkstra算法Floyd算法SPFA算法、引言最短路算法是图论中的核心问题之一，他是许多更深层次算法的基础，同时，该问题有 着大量的生产实际的背景很多问题从表而上看与最短问题没有什么关系却也可以归结为 最短路问题，本文通过收集整理关于最

2、短路径的普遍算法，为研究最短路径问题在一些出行 问题，工程问题，及实际生活问题中的应用，为企业和个人提供方便的选择方法.二、最短路2.1最短路的定义对最短路问题的研究早在上个世纪60年代以前就卓有成效了，其中对赋权(MpO)的有 效算法是由荷兰著名汁算机专家E. W. Dijkstra在1959年首次提出的，该算法能够解决两指 圧点间的最短路，也可以求解图G中一特泄点到英它各顶点的最短路.后来海斯在Dijkstra 算法的基础之上提出了海斯算法但这两种算法都不能解决含有负权的图的最短路问题因 此由Ford提出了 Ford算法，它能有效地解决含有负权的最短路问题.但在现实生活中，我们 所遇到的问

3、题大都不含负权，所以我们在(叫, 0)的情况下选择Dijkstra算法 定义1 若图G = G(V,E)中各边e都赋有一个实数W(e),称为边的权，则称这种图为赋 权图，记为 G = G(V,E,VV).定义2 若图G = G(V,E)是賦权图且W(e) 0,e E(G)，若u是v到v-的路W(“)的权, 则称W(“)为的长，长最小的叫到耳的路W(“)称为最短路.若要找出从片到的通路灯, 使全长最短，即min W (“)= W (e) 2. 2各类最短路算法的齐増2. 2.1 Floyd 算法Floyd算法又称为弗洛伊徳算法，插点法，是一种用于寻找给泄的加权图中顶点间最短 路径的算法该算法名称

4、以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教 授罗伯特弗洛伊徳命名.英核心思路是通过一个图的权值矩阵求岀它的每两点间的最短路径矩阵即从图的带权 邻接矩阵A = “(/ J)打开始,递归地进行n次更新，即由矩阵D(0) = A ,按一个公式，构 造出矩阵2)(1)；又用同样地公式由D(l)构造出D;：最后又用同样的公式由D(l) 构造出矩阵D(n).矩阵(“)的i行丿列元素便是/号顶点到丿号顶点的最短路径长度，称 D(n)为图的距离矩阵，同时还可引入一个后继廿点矩阵path来记录两点间的最短路径.下面介绍其算法过程：1) 从任意一条单边路径开始所有两点之间的距离是边的权，如果两

5、点之间没有边相 连，则权为无穷大；2）对于每一对顶点和卩，看看是否存在一个顶点w使得从到M，再到I，比已知的路 径更短如果是更新它；3）把图用邻接距阵G表示岀来，如果从匕到匕有路可达，则Gi, j = d,d表示该路 的长度；否则GiJ为无穷大；4）泄义一个距阵D用来记录所插入点的信息，Di, j表示从叫到匕需要经过的点， 初始化DiJ = j;5）把备个顶点插入图中，比较插点后的距离与原来的距离，G/J = mm（G/J）, G讥+ G比J,如果GiJ的值变小，则DiJ = k ；6）在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息. 算法Dijkstra（迪杰斯特拉）算

6、法是典型的单源最短路径算法，用于计算一个if点到英他所有节 点的最短路径.主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止.Dijkstra算 法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据 结构，图论，运筹学等等.Dijkstra-般的表述通常有两种方式，一种用永久和临时标号方 式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式.注意该算法要求图下而介绍貝算法过程：首先，引进一个辅助向量，它的每个分虽D表示当前所找到的从始点H到每个终点匕的 最短路径的长度如D3 = 2表示从始点V到终点3的路径相对最小长度为2.这里强调相对就

7、 是说在算法过程中D的值是在不断逼近最终结果但在过程中不一左就等于最短路径长度它 的初始状态为：若从V到岭有弧，则D为弧上的权值：否则为口显然，长度为 Z）j = M/nDIV； eV）的路径就是从V出发的长度最短的一条最短路径.此路径为 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是匕，则可 想而知，这条路径或者是少.叫），或者是（V,V.VA）.它的长度或者是从v到vk的弧上的权 值，或者是DJ和从V.到以的弧上的权值之和.一般情况下，假设S为已求得最短路径的 终点的集合，则可证明：下一条最短路径（设其终点为X ）或者是弧（V,X）,或者是中间 只经过S中的顶点而最后到达

8、顶点X的路径.因此，下一条长度次短的最短路径的长度必是 Dj = MinDW,V其中，或者是弧（匕匕）上的权值，或者是D幻（匕eS）和弧 （匕,匕）上的权值之和.迪杰斯特拉算法描述如下：1）arcs表示弧上的权值.若不存在，则置arcs为8 .S为 已找到从V出发的最短路径的终点的集合，初始状态为空集.那么，从V出发到图上其余各 顶点vi可能达到的最短路径长度的初值为D = arcsLocate Vx（G, V）j（v e v,）,使得 Dj = MinD 乂 e S修改从V出发到集合U -S上任一顶点匕可达的最短路径长度.2. 2. 3 Bel Iman-Ford 算法Dijkstra算法中

9、不允许边的权是负权，如果遇到负权，则可以采用Bellman-Ford算法.Bellman-Ford算法能在更普遍的情况下(存在负权边)解决单源点最短路径问题对于 给泄的带权(有向或无向)图G = (V,E),其源点为S,加权函数W是边集E的映射. 对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点S可 达的负权回路若不存在这样的回路，算法将给岀从源点S到图G的任意顶点V的最短路 径 DV.下而介绍其算法过程：1) 初始化：将除源点外的所有顶点的最短距离估计值DVts,DStO2) 迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点V 的最

10、短距离估计值逐步逼近其最短距离(运行次)：3) 检验负权回路：判断边集E中的每一条边的两个端点是否收敛如果存在未收敛的顶 点，则算法返回false,表明问题无解：否则算法返回tme,并且从源点可达的顶点卩的最 短距离保存在刃中.算法求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm.SPFA算法由西南 交通大学段凡丁于1994年发表.很多时候，给左的图存在负权边，这时类似Dijkstra等算法 便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了.下而介绍其原理与算法过程：我们约定有向加权图G不存在负权回路，即最

11、短路径一泄存在.当然，我们可以在执行 该算法前做一次拓扑排序，以判断是否存在负权回路.我们用数组记录每个结点的最短路径估计值，而且用邻接表来存储图G 我们采取的 方法是松弛：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点 U ,并且用t/点当前的最短路径估计值对离开U点所指向的结点V进行松弛操作，如果V 点的最短路径估计值有所调整，且y点不在当前的队列中，就将H点放入队尾这样不断从 队列中取出结点来进行松弛操作，直至队列空为止.每次将点放入队尾，都是经过松弛操作达到的换言之，每次的优化将会有某个点V的 最短路径估计值变小所以算法的执行会使D越来越小由于我们假泄图中不存在负权

12、 回路，所以每个结点都有最短路径值.因此，算法不会无限执行下去，随着D值的逐渐变小, 直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值.所以只要最短路径存在，上述SPFA算法必定能求出最小值.2.3最短算法的比较2. 3.1 Floyd 算法求多源、无负权边的最短路.用矩阵记录图时效性较差，时间复杂度O(V3).Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一 种算法，可以正确处理有向图或负权的最短路径问题.Floyd-Warshall算法的时间复杂度为0(2)空间复杂度为0(2)Floyd-Wars

13、hall的原理是动态规划：设Dijk为从i到j的只以(1.k)集合中的节点为中间节点的最短路径的长度.若最短路径经过点k ,则Dijk =DiJ,k -1+ Di,j, k若最短路径不经过点k,则Di、j、k= Di,j,k因此，Dijk = min(Di、k，k 一 + Dkjk j、k 一“Dijkstra求单源、无负权的最短路时效性较好，时间复杂度为o(v2 + f).源点可达的话，O(VlgV + ElgU)nO(Elgu).当是稀疏图的情况时，此时E = V2/IgV,所以算法的时间复杂度可为O(V2).若是斐波那 契堆作优先队列的话，算法时间复杂度，则为O(VlgV + E).Be

14、l Iman-Ford求单源最短路，可以判断有无负权回路(若有，则不存在最短路)， 时效性较好，时间复杂度0(VE).Bellman-Ford算法是求解单源最短路径问题的一种算法.单源点的最短路径问题是指：给泄一个加权有向图G和源点s ,对于图G中的任意一点，求从$到“的最短路径.与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数.设想从我们可以从图中找到一个环路(即从卩岀发，经过若干个点之后又回到卩)且 这个环路中所有边的权值之和为负那么通过这个环路，环路中任意两点的最短路径就可以 无穷小下去如果不处理这个负环路，程序就会永远运行下去.而Bellman-Fo

15、rd算法具有分 辨这种负环路的能力.SPFA是Bellman-Ford的队列优化，时效性相对好，时间复杂度O伙e).(k vy 5 = v2,v3,v45v5v6,(1)第一次迭代 计算T(v)J = 2,3,4,5,6如下T(is) = min 丁 (岭),W (气)+ vv12 = min s, 0+5 =5T (巾)=min T (巾),W (片)+ 3 = mi n co, 0+2 = 2 T (v4 ) = min 疗(勺),W (儿)+ vvM = min s, 0+s = s r(v5)=oo,r(v6)=oo 取 m in7，(v;) = 2 = r(v3),lV(v3)=T(

16、y3) = 2 由于 & = 3h(“ = 6),令$ = 卩2，旳，弘， J = 3 转(1) 第二次迭代： 算 7-(v;),j = 2,4,5,6 下T(v2) = min 丁(】勺),W (片)+ = min 5,2 + 1 = 3T (v4 ) = min 7(v4),W(v3) + 畑 = min & 2+8 =8T (也)=min 7 ( v5), W ( v3) + = min 10,2+10 = 10T（v6） = min T（v6）,IV（v3）4- vv36 = min 2+s = o 取 min T（v.） = 3 = T（v2）令 W （v2）=T（v2） = 3 由

17、于 k = 2工（” = 6）,令s = #4,比,i = 2 转（1） 第三次迭代： 算T（v ）,y =4,5,6如下7（v4） = min /（v4）,lV（v2） + w24 = min 8,3+5 = 8T（v5） = min 7（v5）,W（v2）+m5J = min 10,3+9 = 107（v6）= o 取 minr（vJ = 8 = 7（v4）,IV（v4） = T（v4） = 8 由于 = 4工（“ = 6）,令 = 卩5，%” = 4转第四次迭代： 算7（v;）,y=5,6如下7*（吃）=Un 7 他），W （4） + vv,5 = min 10,2 + 8 = 107（

18、i6） = min 丁 （比）,W （q ） + % = min s, 8+5 = 13 取 minT（vf） = 10 = r（v5）JV（v5） = T（v5） = 10 由于R = 5工（” = 6）,令s = %转（1）第五次迭代： 算T（v ）,j=6如下厂（ ）=曲门7 （ % ）, W （匕）+ 吆 = nii n 13,10+2 = 12 由于k=6 = n.因此己找到vj到的最短距离为12.计算结束.找最短路线:逆向追踪得V?| V3 v2 f “4 T V5 f V6最短距离为12,即从城市v,到城市的距离最短,即费用最省.在舰船通道路线设计中的应用利用图论的经典理论和人群

19、流捲理论研究舰船人员通道路线的优化设计及最优线路选 择首先介绍图论相关理论对船舶通道进行路网抽象，建立网络图，然后根据人群流动的相关 理论，选取不同拥挤情况下的人员移动速度，从而确定各条路段（包括楼梯）的行程时间以行程 时间作为通道网络的路权，得出路阻矩阵以选择一对起点/终点的最短时间路线为目标，建立 最短路径问题的数学模型，利用经典的Floyd算法确左最短路径.将此方法应用于某舰艇多层 甲板的通道网络中,计算结果并进行讨论，最后在此研究的基础上对通道设计相关问题的深化 和拓展进行了探讨和总结,并提出设想.路线优化技术通常采用图论中的“图”来表示路网，船舶通道路网与图论的路网对应关 系为:结点

20、通道的交叉口或断头路的终点;边两结点之间的路段称为边,若规左 了路段的方向，则称为弧;边（弧）的权路段某个或某些特征属性的量化表示.路权的标泄决泄了最短的路径搜索依掳，也就是搜索指标根据不同的最优目标,可以选 择不同的路段属性由于舰船上除了平而上的通道之外还有垂直方向的楼梯（或直梯）,如果以 最短路程距离作为优化目标，路线的效率未必最高（距离最短未必耗时最少）所以，以最短行程 时间作为优化的目标，道路权重即为各路段的平均行程时间.对于要研究的对象，取条通道的起点（或终点）和交叉点为图的顶点，各路段为边，路权为 路段行走的平均时间寻找从起点到终点的最短时间路径即为最优路径.在规泄了结点、边和 权

21、值以后，便将路网抽象为一个赋权无向图或賦权有向图，从而确定路网中某两地间的最优路 线便转化为图论中的最短路径问题.首先将空间问题抽象为图，图2为某舰的两层甲板的部分抽象图，上下两个平而上纵横交 错的直线为各层甲板的主要通道，连接两层甲板的直线表示楼梯，包括2个直梯和3个斜梯.每条路段上的标注（d,b）中,表示路段实际长度或者楼梯的类型加：b表示此路段的行 程时间（即路权）3如（40,32）.图2两层甲板的部分抽象图(阳梯6 2$)/丽/(20.16)4032)W.8)也3 220.16)(8) (30.24)进L）（32）：4 8)20.16)(40.32$(1/8)(20,16)(15,12

22、U0J6)图3赋权图再利用上述求最短的方法即可求得需要的通道路线.在工业生产中的应用设备更新问题某企业使用一台设备，在每年年初，企业领导部门就要决左是购置新的, 还是继续使用旧的若购置新设备，就要支付一左的购置费用；若继续使用旧设备，则需支 付一立的维修费用.现在的问题是如何制左一个几年之内的设备更新计划，使得总的支付费 用最少.例如，我们一个五年之内要更新某种设备的计划，若已知该种设备在各年年初的价格 为：第一年第二年第三年第四年第五年1111121213还已知使用不同时间（年）的设备所需要的维修费用为:使用年数0-11-22-33-44 5维修费用5681118可供选择的设备更新方案显然很

23、多的，例如，每年都购置一台新设备，则其购置费用为 11 + 11+12 + 12 + 13=59,而每年支付的维修费用为5,五年合计为25,于是五年总的支付 费用为59+25=84双如决泄在第一、三、五年各购进一台，这个方案的设备购置费为11+12 + 13 = 36, 维修费为5 + 6+5 + 6+5=27五年总的支付费用为63这个例子中一种最佳方案为在第1年、第3年各购宜一台新设备，五年总费用为53.编写一个程序，输入年年初设备的价格与使用不同时间（年）的设备所需要的维修费 用，为该企业领导部门确泄一个方案使得在年内为这台机器支付的总费用最少.3结束语本文将最短路理论应用到实际生活中，尤

24、其是在舰船通道路线中的应用具有很重要的 意义将实际生活中出现的安全隐患尽量降低同时也凸显岀学习和应用最短路问题原理的重 要性.另外，最短路问题在城市道路建设、物资供应站选址等问题上也有很重要的作用.分析 和研究最短路问题趋于热门化.参考文献：王树禾，图论（第二版），科学出版HIMI.2009余为波，基于图论的舰船通道路线优化ML2OO8 李玲屈短路问题在运输网络中的应用M湄华大学出版社.2006 刁在筠,运筹学（第三版）卜几岛等教育出版社.2010谢灼利，地铁车站站台火灾中人员的安全疏散J 中国安全科学学报,200434（7）:21 荣玮基干道路网的锻短路径算法的研究与实现武汉理匸大学出版社.2005 朱建青，张国梁数学建模方法M,郑州大学出版社.杨民助，运筹学小口西安交通大学出版社.般剑宏，吴开亚图论及其算法M中国科学技术出版社.101王朝瑞图论M