第36卷第5期2002年9月
浙 江 大 学 学 报(工学版)
Jo ur nal o f Zhejiang U niv ersity(Eng ineer ing Science)
Vol.36No.5Sep.2002
收稿日期:2001-10-24.
作者简介:柴登峰(1974-),男,浙江江山人,博士生,从事遥感图像处理、地理信息系统方面研究.E-mail:chaidf@z
前N 条最短路径问题的算法及应用
柴登峰,张登荣
(浙江大学空间信息技术研究所,杭州浙江310027)
摘 要:现有最短路径问题指的是狭义最短路径问题,针对该问题而设计的算法只能求得最短的一条路径.前N 条最短路径拓宽了最短路径问题的内涵(即不仅要求得最短路径,还要求得次短、再次短…第N 短路径),是广义最短路径问题.在图论理论基础上分析问题之后,设计了一个递归调用Dijkstr a 算法的新算法,该算法可以求取前N 条最短路径,而且时间、空间复杂度都为多项式阶.该算法已经成功应用于一个交通咨询系统中,自然满足实时应用需要.
关键词:最短路径;N 条最短路径;网络分析;地理信息系统;交通咨询系统
中图分类号:P 208;O 22 文献标识码:A 文章编号:1008-973X (2002)05-0531-04
Algorithm and its application to N shortest paths problem
CHAI Deng-f eng,ZHAN G Deng-rong
(I nstitute of Sp ace and I n f ormation T echnical ,Zhej iang U niv er sity ,H angz hou 310027,China )
Abstract :As the shor test path denotes one path ,algorithms designed for shor test path problem can g et only one path .N shortest paths are N paths including the shortest one ,the one inferior to the shortest one,eto.After reviewing the application of shortest poth pro blem ,an N shortest paths problem w as put fo rw ard and described.Gr aph theo ry w as used to analy ze the problem and results in fo ur theoretical con-clusions .T hen ,algo rithm recursively calling the Dijkstra algor ithm was desig ned and analy zed .Bath time co nplexity and space conplex ity are poly nom ial order.The algo rithm w as tested by ex periment and applied to a traffic consultatio n system of Guang zhou City ,it can meet the need of r eal-time application.Key words :sho rtest path;N shor test paths;netw ork analysis;tr affic consultation system ;GIS 20世纪中后期,随着计算机的出现和发展,图论的理论和应用研究得到广泛重视,图论作为一个数学分支的地位真正得到了确立.现在,图论的应用已经深入到众多领域,GIS 网络分析就是图论在地理信息领域的重要应用[3]
,此外,还有城市规划、电子导航、交通咨询等等.
最短路径问题是图论中的一个典范问题[1],主要研究成果有Dijkstra 、Floy d 等优秀算法[1,2],Dijk-stra 还被认为是图论中的好算法[1]
.目前的研究工作主要集中于算法实现的优化改进与应用方面[3,4].最短路径问题通常有两类[2]:一类是求取从某一源点到其余各点的最短路径;另一类是求取每一对顶
点之间的最短路径.它们从不同的角度描述问题,但有一个共同的缺陷:这里的最短路径指两点之间最
短的那一条路径,不包括次短、再次短等等路径.在此不妨称以上两类问题为狭义最短路径问题,为此设计的算法只能求得最短的一条路径,而不能得到次短、再次短等等路径.
实际上,用户在使用咨询系统或决策支持系统时,希望得到最优的决策参考外,还希望得到次优、再次优等决策参考,这同样反映在最短路径问题上.因此,有必要将最短路径问题予以扩充,成为N 条最短路径问题,即不但要求得到最短路径,还要得到次短、再次短等路径.这称之为广义最短路径问题.
1 问题描述
在图、有向图、赋权图、顶点、边、路径(或称为通路、路)以及路径的长度等概念[2]的基础上,下面给出前N条最短路径问题的定义.
前N条最短路径问题是:设有赋权图G(V,E)及其上给定的两个顶点v i和v j,r为v i和v j之间的一条路径,记其长度为d(r),由v i和v j之间的所有互不相同的路径组成的集合R(G,v i,v j)称为G上v i和v j之间的路径集合,即R(G,v i,v j)={rûr为G 上v i,v j之间的路径}.若按路径长度值大小将其排列得r1,r2,…,r M,d(r1)≤d(r2)≤…≤d(r M),则称r1为G上v i和v j间的第1最短路径(即狭义最短路径),d1为其长度;r2为G上v i和v j间第2最短路径,d2为其长度;r M为G上v i和v j间第M最短路径,d M为其长度.求取G上v i和v j间的第1～N(N ≤M)最短路径的问题称为前N条最短路径问题.
2 算法设计的理论基础
前面已指出,Dijkstra算法是求解狭义最短路径问题的优秀算法,但它只能求取第1最短路径而不能求得第2,…,N最短路径.经对问题研究分析后,归纳总结出四个结论,据此可将前N条最短路径问题转换为狭义最短路径问题加以求解.这样,就可以借用Dijkstra算法求解前N条最短路径问题.
在给出结论之前,先作如下约定:
(1)文中所指子图皆为生成子图.
(2)r1(G,v i,v j)为G上v i和v j间的第1最短路径.
结论1:若r=v0e1v1…e n v n∈R(G,v i,v j),则存在G′A G,使得r=r1(G′,v i,v j),反之,若G′A G,则R(G′,v i,v j)A R(G,v i,v j).
结论2:r=r1(G,v i,v j),r′=r1(G′,v i,v j),若G′(V,E′)A G(V,E),则d(r)≤d(r′).
结论3:设R(G,v i,v j)={r1,r2,…,r M},d(r1)≤d(r2)≤…≤d(r M),r1=v0e1v1…e n v n,R′(G,v i,v j) =∪
k=1,…,n
R k(G k,v i,v j),R k(G k,v i,v j)=R(G k(V,E k), v i,v j),E k=E(G)-{e k},则R(G,v i,v j)-{r1}=
R′(G,v i,v j).
结论4:设R(G,v i,v j)={r1,r2,…,r M},d(r1)≤d(r2)≤…≤d(r M),r′k=r1(G k,v i,v j),R k=R(G k,
v i,v j)-{r′k},G k A G,k=1,…,n,R′=∪
k=1,…,n ({r′k}∪
R k),则有:
¹若{r s,…,r M}=R′,d(r′t)=min
k=1,…,n
(d(r′k)),则r s=r′t.
º若r′t=v0e1v1…e m v m,则{r s+1,…,r M}=R″, R″=(∪
k=1,…,n,r′
k
≠r′
t
({r′k}∪R k))∪(∪
p
(∪
l
({r p l}∪R p l))),R p l=R(G p l,v i,v j),r p l=r1(G p l,v i,v j),G p l(V,
E p l),E p l=E p-{e l},l=1,…,m,p∈{1,…,n},r′p=r s,
且 r s+1=
r′t,d(r′t)=min(m in
k=1,…,n,r′
k
≠r′
(d(r′k)),
m in
p∈{1,…,n},r′
p
=r′
l
(min
l=1,…,m
(d(r p l))));
r q t,d(r q t)=m in(min
k=1,…,n,r′
k
≠r′
(d(r′k)),
m in
p∈{1,…,n},r′
p
-r′
t
(min
l=1,…,m
(d(r p l)))).
根据结论1,赋权图G(V,E)上两顶点间的任一路径都必然是它的某一子图G′(V,E′)上相同顶点
间的第1最短路径,可将一个图G(V,E)上两顶点
间的第2,…,N最短路径转换为第1最短路径加以
求解.根据结论3,可将第1最短路径r1从路径集合
{r1,r2,…,r M}中分离出来,分别将第1最短路径r1
=v0e1v1,…,e n v n上的一条边从图G的边集中删除
就可得到一批子图G k,k=1,…,n,这些子图上路径
集合的并集∪
k=1,…,n
R k就等于非第1最短路径集合{r2,…,r M}.同样,可将路径集合R k,k=1,…,n分
离为第1和非第1最短路径.如此递归进行可将全
部路径转化为某一子图上的第1最短路径.
将所有路径全部求出,然后按路径长度值大小对其进行排序即可求解前N条最短路径问题.在实
际应用中N通常较小(N<5),避免求取不必要的
路径是算法设计的关键.根据结论4,如果前s-1最
短路径r1,r2,…,r s-1已经求得且所剩路径r s,…,r M
在若干子图(它们组成一子图集)上路径集合R k,k
=1,…,n中,则第s最短路径r s是这些子图上第1
最短路径的最短者,求得第s最短路径后,在子图集
中将第s最短路径所对应的子图(该子图的第1最
短路径为原图的第s最短路径)用若干子图(根据结
论3求得)取代,得到新的子图集就是求取第s+1
最短路径所需的子图集.当s=1时,原图就是所需
子图,求得第1最短路径之后,派生出若干子图,这
样可以求取第2最短路径,如此递推进行,直至求取
第N最短路径.这就不必求出全部路径,在N较小
时,就显得更加重要和有效.上述四个结论是算法设
计的理论依据.
532浙 江 大 学 学 报(工学版) 第36卷
