龙源期刊网 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