求解K最短路径的改进Dijkstra算法

求解K最短路径的改进Dijkstra算法

张嵩王军马金平

本研究得到山东省教育厅科技计划项目（No：J07WJ09）和青岛市社会科学规划研究项目（No：QDSKL070115）资助。

青岛大学青岛266071

摘要：本文首先从轨道交通和常规交通的衔接规划的视角，阐述了求解K最短路径问题在公交线网优化中的意义。然后在Dijkstra最短路算法的基础上，创造性地引入了多个P标和多个T标来记录起点到该节点的K短路径及其上界，使改进后的算法成功求解K最短路径。最后用C语言对算法进行实现，并随机产生测试数据进行算法测试，测试结果表明了该算法的计算效率和应用前景。

关键词：Dijkstra算法K最短路径公共交通衔接规划SolvesKmostshortpathimprovementDijkstraalgorithm

ZhangSongWangJunMaJinping

Abstract:Thisarticlefirstfromtheorbitaltransportationandtheconventionaltransportationengagementplanangleofview,elaboratedsolvestheKmostshortpathquestiontooptimizeinthepublictransportationwirethesignificance.ThenmostshortcircuitsinDijkstrainthealgorithmfoundation,creativelyhasintroducedmanyPsignandmanyTsignrecordsthebeginningtothisnodeKshortpathandtheupperboundary,aftermakestheimprovementthealgorithmsuccesstosolvetheKmostshortpath.FinallyusestheClanguagetocarryontherealizationtothealgorithm,andhadthetestdatatocarryonthealgorithmteststochastically,thetestresulthasindicatedthisalgorithmcountingyieldandtheapplicationprospect.

Keywords:DijkstraalgorithmKmostshortpathMasstransitEngagementplan

【中图分类号】F542【文献标识码】C【文章编号】1009-9646(2009)04-0029-03

1．引言

最短路径问题是网络分析中最基本的组合优化问题之一，在公交线网规划中的应用十分广泛。尤其是随着我国经济的飞速发展和城市化进程的加快，城市轨道交通已进入大发展时期。作为城市客运交通骨干，轨道交通应该与常规公交、铁路客运、公路客运、航空客运、小汽车、自行车和步行等多种交通方式密切配合，这就对城市交通的发展提出了衔接规划的要求。轨道交通的衔接规划是基于轨道交通的发展,对其沿线的交通资源配置优化和整合,达到客运交通资源最优化。其中很重要的任务就是对现有城市公交线网进行重新规划。然而在实际进行公交线网优化设计中，最短路径模型往往无法直接应用。原因主要有两个方面：首先，在线网规划中往往要求公交路线必需经过某些指定路段（地铁终点站、主要接驳站等），或者必需不经过某些指定路段（与地铁线路重复的路段、需要抽疏的路段等），从而出现了指定路线的最短路径问题。其次，在线网规划中有很多无法通过数学模型具体表达的要求，决策者往往需要多个线路设计方案，并从中进行决策，从而出现了K最短路径问题。

在非负权网络最短路径问题中，最有效的方法是Dijkstra算法［1］。基于这个算法，还出现了一些对Dijkstra算法的扩展和改进［2］，其中具有代表性的是TQQ、DKA、DKD［3］、HOPA［4］、A*算法［5］等。对于K最短路径问题，Yen提出了递推算法［6］，基于动态规划，李成江提出了复杂度为0(m+nlgn+mlgk)的算法［7］。由于Dijkstra算法的高效性和易扩展性，本文在经典的Dijkstra算法的基础上，提出了新的求解K最短路径的算法。

2.求解K最短路径的改进Dijkstra算法

对于一个具有n个节点和m条边的非负权有向网络G(V,E,L)，Dijkstra算法求解起点vs到vt的最短路径的基本思想是：如果节点序列{vs,…,vi,vt}是从vs到vt的最短路径，则{vs,…,vi}必为从vs到vi的最短路径，即从起点到某节点的最短路权一定是它全部紧前节点的最短路权与相应路权之和的最小值。在Dijkstra算法中，对每个节点进行标号，或者是试探性T标号，或者永久性P标号。T(vi)标号表示从vs到vi的最短路权的上界，是一种临时标号。P(vi)标号表示从vs到vi的最短路权，该标号一旦确定不再改变。算法的过程是不断修正节点的T标号值，将最小T标号修改为该节点的P标号，直至得到vt的P标号。

在K最短路径问题中，我们注意到从起点vs到节点vi的第k短路权，k=1,…K，一定是vs到vi的全部紧前节点的前k短路权与相应路权之和的第k小值。因此，计算节点vi的第k短路径时只需考虑vi的全部紧前节点的前k短路径。为了记录前K短路径，我们需要为每个节点设置K个标号，或者是试探性T标号，或者永久性P标号。Tk(vi)表示起点vs到vi的第k短路径路权的上界；Pk(vi)表示起点vs到vi的k最短路权值，而且一定有T1(vi)≤T2(vi)≤…≤TK(vi)，P1(vi)≤P2(vi)≤…≤PK(vi)。在算法中，我们需要不断修正节点的K个T标号，将其中最小的T标号修改为该节点相应的P标号，直到得到PK(vi)为止。具体步骤如下：

步骤0.给vs以P标号，P1(vs)=0；

其余各点均给T标号，Tk(vi)=+∞,vi∈V/{vs},k=1,…,K。

步骤1.vi为刚得到Pk(vi)标号的节点，考虑节点vj:(vi,vj)∈E。

(1)如果Pk(vi)+lij＜Tk(vj)，确定一个q值，满足

Tq-1(vj)≤pk(vi)+lij＜Tq(vj)

(2)将Pk(vi)+lij按照q值插入vj的K个T标中，即

Tk(vj)Tk-1(vj),Tk-1(vj)Tk-2(vj),…,Tq+1(vj)Tq(vj),Tq(vj)Pt(vj)+lij

步骤2.比较所有T标号的值，将最小的T标号改为相应的P标号，即

Pk*（vj*）Tk*(vj*)=mink,j{Tk(vj)}，记录(vi,vj*)。

如果存在多个最小者时，将它们同时改为P标号；

如果Pk(vt)已经标出，算法结束；否则，返回步骤1。

3.算例求解

下面我们用一个算例来说明新算法的步骤。求解网络中从v0到v4的前3短路径。

步骤0，P1(v0)=0,Tk(vi)=+∞,i=1,…,4,k=1,2,3。

迭代一.（v0）：

步骤1，考虑节点v1、v2，计算其T标号值：

P1(v0)+l01=0+2＜T3(v1)=+∞，得到q=1，T3(v1)=T2(v1)=+∞，

T2(v1)=T1(v1)=+∞，T1(v1)=P1(v0)+l01=2；

p1(v0)+l02=0+3＜T3(v2)=+∞，得到q=1，T3(v2)=T2(v2)=+∞，

T2(v2)=T1(v2)=+∞，T1(v2)=P1(v0)+l02=3。

步骤2，比较所有标号，T1(v1)=2是最小的T标号，将其改为P1(v1)=2，记录(v0，v1)。

迭代二.（v1）：

步骤1,考虑v2、v3、v4，计算其T标号值：

P1(v1)+l12=2+2＜T3(v2)=+∞，得到q=2，T3(v2)=T2(v2)=+∞，

T2(v2)=P1(v1)+l12=4；

P1(v1)+l13=2+5＜T3(v3)=+∞，得到q=1，T3(v3)=T2(v3)=+∞，

T2(v3)=T1(v3)=+∞,T1(v3)=P1(v1)+l13=7；

P1(v1)+l14=2+1＜T3(v4)=+∞，得到q=1，T3(v4)=T2(v4)=+∞，

T2(v4)=T1(v4)=+∞,T1(v4)=P1(v1)+l14=3；

步骤2，比较所有的T标号，T1(v2)=T1(v4)=3最小，P1(v2)=3，记录(v0,v2)，

P1(v4)=3，记录(v1,v4)。

迭代三.（v2）：由于v4没有紧后节点，故不考虑。

步骤1，考虑节点v1、v3、v4，计算其T标号值：

P1(v2)+l21=3+2＜T3(v1)=+∞，得到q=2，T3(v1)=T2(v1)=+∞，

T2(v1)=P1(v2)+l21=5；

P1(v2)+l23=3+3＜T3(v3)=+∞，得到q=1，T3(v3)=T2(v3)=+∞，

T2(v3)=T1(v3)=7,T1(v3)=P1(v2)+l23=6；

P1(v2)+l24=3+4＜T3(v4)=+∞，得到q=2，T3(v4)=T2(v4)=+∞，

T2(v4)=P1(v2)+l24=7；

步骤2，比较所有T标号，T2（v2）=4最小，P2(v2)=4，记录(v1,v2)。

继续迭代，直至得到P3(v4)=7，并得到从v0到v4的前三短路为分别为v0→v1→v4，v0→v2→v1→v4和v0→v2→v4，它们的路权分别为3，6和7。

4.算法测试

本算法用C语言实现，并对算法进行了测试。测试环境为：MicrosoftWindowsXPServicePack4；Inter(R)Core(TM)2DuoCPU1.5GHz；PhysMemory：1023MBDDR2-667MHz。用伪随机数随机生成网络邻接矩阵，产生不同规模的问题，n=20,40,60,80,100，每种规模生成10个问题，分别计算前2，3，4短路径，统计计算所需的CPU时间（单位秒）

当前节点考虑节点标号最小标号修改后标号初始值v0p1=0v1T1=∞,T2=∞,T3=∞v2T1=∞,T2=∞,T3=∞v3T1=∞,T2=∞,T3=∞v4T1=∞,T2=∞,T3=∞

迭代一v0v1T1=2,T2=∞,T3=∞T1=2P1=2,T2=∞,T3=∞v2T1=3,T2=∞,T3=∞

迭代二v1v2T1=3,T2=4,T3=∞T1=3P1=3,T2=4,T3=∞v3T1=7,T2=∞,T3=∞v4T1=3,T2=∞,T3=∞T1=3P1=3,T2=∞,T3=∞

迭代三v2v1P1=2,T2=5,T3=∞v3T1=6,T2=7,T3=∞v4P1=3,T2=7,T3=∞*v2P1=3,T2=4,T3=∞T2=4P1=3,P2=4,T3=∞v4不指向任何节点

迭代四v2v1P1=2,T2=5,T3=6T2=5P1=2,P2=5,T3=6v3T1=6,T2=7,T3=7v4P1=3,T2=7,T3=8

迭代五v1v2P1=3,P2=4,T3=7v3T1=6,T2=7,T3=7T1=6P1=6,T2=7,T3=7v4P1=3,T2=6,T3=7T2=6P1=3,P2=6,T3=7*v1P1=2,P2=5,T3=6T3=6P1=2,P2=5,T3=6

迭代六v1v2P1=3,P2=4,T3=7v3P1=3,T2=7,T3=7T3=7P1=3,P2=7,P3=7v4P1=3,P2=6,T3=7v3v2P1=3,P2=4,T3=7T2=T3=7P1=3,P2=4,P3=7v4P1=3,P2=6,T3=7T3=7P1=3,P2=6,P3=7v4不指向任何节点

内存溢出100内存溢出从统计结果可知，本算法求解100个节点的网络前2短路径平均需要CPU时间12.4秒。在测试环境内存的限制下，求解前3短路径时最多可以计算80个节点的网络，而求解前4短路径时最多可以计算60个节点的网络。

根据以上计算结果，可以相信在计算机内存可以保证的条件下，能够计算200个节点的网络前5最短路径问题，满足城市公交线网优化的要求。

参考文献

［1］DijkstraE.W.Anoteontwoproblemsinconnexionwithgraphs［J］.NumerischeMathematik,1959,1:269~271

［2］XuM.H.，LiuY.Q.，HuangQ.L.,ZhangY.X.,LuanG.F.AnimprovedDijkstrasshortestpathalgorithmforsparsenetwork［J］.AppliedMathematicsandComputation,2007,185:247~254

［3］ZhanFB.Threefastestshortestpathalgorithmsonrealroadnetworks［J］.JournalofGeographicInformationandDecisionAnalysis,1997,1(1):69~82

［4］王景存、张晓彤、陈彬、陈和平.一种基于Dijkstra算法的启发式最优路径搜索算法［J］.北京科技大学学报,2007，3（3）：346~350

［5］RothkopfH,StarkRM.Competitivebidding:Acomprehensivebibliography［J］.OperationsResearch,1979,27(2):365~390

［6］YenJ.Y.Findingthekshortestlooplesspathesinanetwork［J］,ManagementScience,1971,17:712~716

［7］李成江.新的K最短路算法［J］.山东大学学报(理学版),2006,41(4):40~43