关于最短路径的SPFA快速算法_段凡丁

《关于最短路径的SPFA快速算法_段凡丁》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、..99Voo第卷第期西南交通大学学报2JJGIII99SS99SPVVUUUF1年月1丫·YPSF关于最短路径的快速算法段凡丁()11西南交通大学0计0算中心成都PP(oFF【摘要】本文提出了关于最短路径问题的一种新的快速算法baha.,—mP)F即ih算法算法采用动态优化逼近的方法用邻接表作为有向图的存储结r,用了一个先进先出的队列归eu。。构Q来作为待优化点的存储池算法的时间复杂性为o,,。.。,,sA(e)在绝大多数情况下图的边数和顶点数的关系是<矛因此PF算法比.经典的创归tar算法在时间复杂性方面更优越【关键词】;;;有向图最短路径算法时间复杂性【分类号】1

2、甲312在计算机网络、交通运输工程、通信工程等各种应用中,常常需要计算图中从某个源点到其余各顶点的最短路径或各顶点之间的最短路径。很多的优化问题在数学上讲,是相当于找寻一个图中的最短路径.因此,在图论中,最短路径算法比其它算法研究得更为透彻。到1974年,。,为止大约有10多篇论文和几十种算法已经提出来了lj[关于单源最短路径的算法目前最a,2。,ae:流行的经典算法是iDjkstr算法它的时问复杂性是口(矿)[〕197峨年wgn采用桶分类得。,。出一个口()的算法但必须是边的权值是小的整数才适用3j[关于每一对顶点之间的最短路,,。3。径算法公认lFoyed算法最佳其

3、时间复杂性为。(.)[〕本文对最短路径问题的这两个方面,,。,。,进行研究提出了一种新的快速算法sPFAsPFA算法的时问复杂性为口()当《妒时—。,sPFA算法表现出时问复杂性上的优越sPFA算法对边的权值没有特殊的限制适合于任意有向图。1单源最短路径的SPFA算法1.1Dij如tar算法分析,:为了清楚起见和便于比较现将iDjkstar算法简述如下(nl)besi(。。;2)s~{)(3)刀。。0;〔〕,ore。in。。o。v。,。;(4)rcahF一{}d。〔〕,l()(5)whiles护Vdobegin19939。本文于年月20收到西南交通大学学报第卷’wmmm

4、rxeeeee()不一ni〔。〕niidd()功’rde()卜一nievD。,Dw,。;(,)刀[〕~M创(〔〕[]+l(w))end(10)endiDstra。:kj算法采用了两个集合这样的数据结构来安排图的顶点算法的主要思想是从有一,,向图的Vs集合中选取具有最小D[w」的点w尔后把w点放入s集合中那么s集合就是已经。。计算出具有最短路径的点的集合然后再从卜s集合中将所有经过点。而与源点相通的点的。。l,。。路径值D[〕统统都作调整(如果存在D[」>D[wj十w()的话)重复此过程直到所有的点。全部进入s集合_,,一从以h分析可以看出DIJkstra算法属于探新法的

5、一种即每次都是从Vs集合中选一个,。具有最小D「。]的点并放入S集合进入了s集合的点的路径值就保证是该点的最短路径,即循环的每一步都能正确地算出从源点到。算法是一步一个脚印地向前搜索点的最短,一_w。路径D「]并且将所有的经过w点的fs集合的点的路径值都作相应的优化从时问仁来分,忍,O,,。,we,析若有个顶点的图则第(6)句为()第(8)句为。()这两项是并列在hil循环里的e。,02,。2。而whil循环也是。()故总的时liIJ为0(2)简算为o()数量级1.2sPFA算法描述,,l,输人设L是用来表示有向图G=(v)E的邻接表邻接表元素是有向图各边的权值,。输入

6、各边的权值lv(k)建立邻接表L,输出设D数组是记录当前从源点到其余各点的最短路径的值初始化时D数组的每个,。元素都为最大值经过sPFA算法D数组输出各点的最短路径值,。方法SPFA算法采用图的存储结构是邻接表方法是动态优化逼近法算法中设立了一,,个先进先出的队列oewQue用来保存待优化的顶点优化时从此队列里顺序取出一个点并且,,,用w点的当前路径D「w]去优化调整其它各点的路径值D「月若有调整即D「月的值改小了]点放ue。ue就将入Qeu队列以待继续进一步优化反复从Que队列里取出点来对当前最短路,,径进行优化直至队空不需要再优化为止此时D数组里就保存了从源点到各点

7、的最短路径。:值SPFA算法的形式算法描述及注释如下(])besin{算法开始}’oreh砂in不do(2)feabeginoreh无vdordz。,无;fea〔L[]ea(()){读入每条边的权值到邻接表}。:;QM[」=0(初始化每个顶点是否在队里的标志数组)Dv,;〔]=MAX第期段凡丁关于最短路径的PS快速算法}将最短路径数组初始化为最大值eeeuuQo。。QM〔〕eeuu。。}源点人Q队。。j〔}源点到源点本身的路径值赋值为零ieeeeyhwmuuQPooiegbeewuuQeewuu从Q队列里取出一个点wQM,,咬,表示w点不