龙源期刊网 http://www.qikan.com.cn
改进型Dijkstra算法的最短路径求解
作者:金婷 方欢 方贤文 来源:《软件导刊》2016年第02期
摘要摘要:最短路径问题一直是图论中的研究热点。为寻找有向图中任意两点之间存在的所有最短路径,从Dijkstra算法入手,分析其最短路径实现原理,发现其局限性,即多条路径求解是唯一的;对算法作出改进,在Dijkstra算法基础上引入前置邻结点,对每个顶点增加前置邻结点属性,并进行实时记录和更新,使改进后的算法能够求解多条路径问题。利用Java语言编程实现算法思想,通过简单的界面显示验证了算法的正确性。 关键词关键词:Dijkstra算法;前置邻结点;多条最短路径 DOIDOI:10.11907/rjdk.1511199 中图分类号:TP319
文献标识码:A文章编号文章编号 :16727800(2016)002012903 0引言
现实生活中的很多问题都可以归结为最短路径问题,最短路径不仅是局限于空间位置上的距离最短,也可能是指最少交通费用,或者是最短运输时间等。Dijkstra算法是公认的求解最短路径的较好算法,旨在计算一个节点到其它所有节点的最短路径。在Dijkstra算法优化方面,国内外学者提出了多种方法,包括DKB、DKD、二叉堆法等[12]。Dijkstra算法的具体应用研究也涉及到生活的方方面面,比如,农产品配送、城市交通系统等。对于给定有向图,确定起点终点的最短路径问题,需要对经典的Dijkstra算法作出适当改进,使其终点一经标号即结束循环,输出最短距离和存在的多条最短路径。 1基于Dijkstra算法的最短路径求解
Dijkstra算法按路径长度的非降次序生成有向图中某个指定结点(源点)到其它各结点的最短路径。例:有向图如图1所示,求图1中源点到其它各顶点的最短路径。
该图的成本邻接矩阵为:0205030∞∞∞025∞∞70∞∞0402550∞∞∞∞55∞∞∞∞∞010∞∞∞∞∞0 S集合存放已经生成最短路径的顶点,COST(i,j)是边[i,j]的权DIST(j)被置以源点到结点j的最短路径长度。V0是源点,首先将结点V0放入S中。此时DIST(1)最小为20,
龙源期刊网 http://www.qikan.com.cn
说明V0到V1的最短路径为20。将结点1计入S中,注意此时DIST(w)(w=2,3,4,5)的值可能发生变化,如果DIST(w)>DIST(1)+COST(1,w),则将 2Dijkstra算法改进
为了使Dijkstra算法也能应用于多条路径问题,需要对算法作出改进,引入前置邻结点,并考虑DIST(w)=DIST(m)+COST(m,w)的情况。 2.1解决方案
G是一个n结点有向图,它由其成本邻接矩阵COST(n,n)表示,DIST(j)被置以源点start到结点j的最短路径长度。Step1:初始化每个顶点的前置邻结点、前置邻接点数、最短路径数量以及具体路径。对于每个不在集合S且与源结点存在直接通路的点,将它们的前置邻结点设为start,前置邻结点的个数为1,最短路径就是源点到顶点的直接通路。其它结点前置邻结点数为0,不存在最短路径。只有源点在集合S中,也称该顶点被标号。Step2:寻找下一个被放进集合S的顶点:①找到没有被标号其最短路径的顶点m;②判断m是否与给定的结束点相同,如果相同,返回最短路径,退出。否则,进入Step3。Step3:对于每一个不在S集合且与顶点m直接相连的顶点x作如下判断:(1)顶点x现有的最短路径长度>源点经过顶点m到x的路径长度,则:顶点x的最短路径长度为顶点m的最短路径长度与m到x的路径之和;顶点x的最短路径个数为顶点m的最短路径个数;顶点x的最短路径为顶点m的最短路径连接x;置顶点x的前置邻结点为m,个数为1。
(2)顶点x现有的最短路径长度=源点经过顶点m到x的路径长度,则:顶点x的最短路径个数=顶点x现有的最短路径个数与顶点v的最短路径个数之和;顶点x的最短路径连接m加入顶点x现有的最短路径;顶点x的前置邻结点加上m;顶点x的前置邻结点的个数加上1;转Step2[4]。
2.2生成多条最短路径的贪心算法
Procedure ShortestPaths(start,end,COST,DIST,n)
boolean S[0,n-1];int m,COST[0,n-1;0,n-1],DIST[0,n-1],MinPathNum[n], MinPath[n][m],PreVertexNum[n],PreVertexID[n];
for i←0 to n-1 do//每个顶点的前置结点个数为0,最短路径的条数也为0 S[i]=0;
DIST[i]←COST[start][i];
龙源期刊网 http://www.qikan.com.cn
if S(i)=0 and DIST[i] not and DIST[i] not 0//找出每个不在S的节点中与源节点存在直接通路的点,将它们的前置邻结点设为start,前置邻结点的个数为1。 MinPathNum[i]=1; MinPath[i][0].add(start); MinPath[i][0].add(i); PreVertexNum[i]=1; PreVertexID[i].add(start); end if
PreVertexNum[i]=0; MinPathNum[i]=0; repeat S[start]=1;
MinPathNum[start]=1; MinPath[start][0]=start; PreVertexNum[start]=0; for num←1 to n-1 do
find DIST[num] is the minimum and num is not in S S[num]=1; if(num==last)
return MinPath[num][m];
for all vertex w S(w)==0 and COST[num][w]!= and DIST[num]!=infinite do