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

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

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

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

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

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

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

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

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

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