關(guān)于最短路徑的SPFA快速算法.pdf

《關(guān)于最短路徑的SPFA快速算法.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、..第29卷第2期西南交通大學學報Vol29No21994年4月JOURNALOFSOUTH丫VESTJIAOTONGUNIVERSITYAPt·1994關(guān)于最短路徑的SPFA快速算法段凡丁(西南交通大學計算中心成都610031)FA(thFaster【摘要】本文提出了關(guān)于最短路徑問題的一種新的快速算法sPsbortesPa.,—Al即rithm)算法sPFA算法采用動態(tài)優(yōu)化逼近的方法用鄰接表作為有向圖的存儲結(jié),用了一個先進先出的隊列歸eu。。構(gòu)Q來作為待優(yōu)化點的存儲池算法的時間復雜性為o,,。.。,,sA(e)在絕大多

2、數(shù)情況下圖的邊數(shù)和頂點數(shù)的關(guān)系是<矛因此PF算法比.經(jīng)典的創(chuàng)歸tra算法在時間復雜性方面更優(yōu)越【關(guān)鍵詞】;;;有向圖最短路徑算法時間復雜性【分類號】1甲312在計算機網(wǎng)絡、交通運輸工程、通信工程等各種應用中,常常需要計算圖中從某個源點到其余各頂點的最短路徑或各頂點之間的最短路徑。很多的優(yōu)化問題在數(shù)學上講,是相當于找尋一個圖中的最短路徑.因此,在圖論中,最短路徑算法比其它算法研究得更為透徹。到1974年,。,為止大約有10多篇論文和幾十種算法已經(jīng)提出來了[lj關(guān)于單源最短路徑的算法目前最a,2。,ae:流行的經(jīng)典算法是Di

3、jkstr算法它的時問復雜性是口(礦)[〕197峨年wgn采用桶分類得。,。出一個口()的算法但必須是邊的權(quán)值是小的整數(shù)才適用[3j關(guān)于每一對頂點之間的最短路,,。3。徑算法公認Floyed算法最佳其時間復雜性為。()[.〕本文對最短路徑問題的這兩個方面,,。,。,進行研究提出了一種新的快速算法sPFAsPFA算法的時問復雜性為口()當《妒時—。,sPFA算法表現(xiàn)出時問復雜性上的優(yōu)越sPFA算法對邊的權(quán)值沒有特殊的限制適合于任意有向圖。1單源最短路徑的SPFA算法1.1Dij如tra算法分析,:為了清楚起見和便于比較現(xiàn)將

4、Dijkstra算法簡述如下(nl)besi(。。;2)s~{)(3)刀。。0;〔〕,ore。in。。o。v。,。;(4)rcahF一{}d?！病?l()(5)whiles護Vdobegin19939。本文于年月20收到208西南交通大學學報第29卷’(6)eheavertexwin不一5suehthatD〔。〕15aminimum;os(7)add功tos;orv’(8)feaehin卜一5dovD。,Dw,。;(,)刀[〕~M創(chuàng)(〔〕[]+l(w))end(10)endDistra。:jk算法采用了兩個集合這樣的數(shù)據(jù)

5、結(jié)構(gòu)來安排圖的頂點算法的主要思想是從有一,,向圖的Vs集合中選取具有最小D[w」的點w爾后把w點放入s集合中那么s集合就是已經(jīng)。。計算出具有最短路徑的點的集合然后再從卜s集合中將所有經(jīng)過點。而與源點相通的點的。。l,。。路徑值D[〕統(tǒng)統(tǒng)都作調(diào)整(如果存在D[」>D[wj十(w)的話)重復此過程直到所有的點。全部進入s集合_,,一從以h分析可以看出DIJkstra算法屬于探新法的一種即每次都是從Vs集合中選一個,。具有最小D「。]的點并放入S集合進入了s集合的點的路徑值就保證是該點的最短路徑,即循環(huán)的每一步都能正確地算出從

6、源點到。算法是一步一個腳印地向前搜索點的最短,一_w。路徑D「]并且將所有的經(jīng)過w點的fs集合的點的路徑值都作相應的優(yōu)化從時問仁來分,忍,O,,。,we,析若有個頂點的圖則第(6)句為()第(8)句為。()這兩項是并列在hil循環(huán)里的e。,02,。2。而whil循環(huán)也是。()故總的時liIJ為0(2)簡算為o()數(shù)量級1.2sPFA算法描述,,l,輸人設L是用來表示有向圖G=(vE)的鄰接表鄰接表元素是有向圖各邊的權(quán)值,。輸入各邊的權(quán)值l(vk)建立鄰接表L,輸出設D數(shù)組是記錄當前從源點到其余各點的最短路徑的值初始化時D

7、數(shù)組的每個,。元素都為最大值經(jīng)過sPFA算法D數(shù)組輸出各點的最短路徑值,。方法SPFA算法采用圖的存儲結(jié)構(gòu)是鄰接表方法是動態(tài)優(yōu)化逼近法算法中設立了一,,個先進先出的隊列oewQue用來保存待優(yōu)化的頂點優(yōu)化時從此隊列里順序取出一個點并且,,,用w點的當前路徑D「w]去優(yōu)化調(diào)整其它各點的路徑值D「月若有調(diào)整即D「月的值改小了]點放ue。ue就將入Qeu隊列以待繼續(xù)進一步優(yōu)化反復從Que隊列里取出點來對當前最短路,,徑進行優(yōu)化直至隊空不需要再優(yōu)化為止此時D數(shù)組里就保存了從源點到各點的最短路徑。:值SPFA算法的形式算法描述及注

8、釋如下(])besin{算法開始}’oreh砂in不do(2)feabeginoreh無vdordz。,無;fea〔L[]ea(()){讀入每條邊的權(quán)值到鄰接表}。:;QM[」=0(初始化每個頂點是否在隊里的標志數(shù)組)Dv,;〔]=MAX2:第期段凡丁關(guān)于最短路徑的SPFA快速算法209{將最短路徑數(shù)組初始化為最大值