資源描述：
《SPFA算法的分析及改進(jìn)-論文.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第41卷第6期計(jì)算機(jī)科學(xué)Vo1．41No．62014年6月ComputerScienceJune2014SPFA算法的分析及改進(jìn)夏正冬b天明張居陽(yáng)(華東師范大學(xué)上海市可信重點(diǎn)實(shí)驗(yàn)室上海200062)摘要SPFA(ShortestPathFasterAlgorithm)算法是一種對(duì)任意有向圖求單源最短路徑的算法。該算法實(shí)現(xiàn)簡(jiǎn)單，實(shí)際運(yùn)行效果較好，在國(guó)內(nèi)有著比較大的影響力。但遺憾的是，該算法一直缺少正確的理論分析。對(duì)該算法進(jìn)行了分析，指出該算法在不存在源點(diǎn)可達(dá)負(fù)圈的有向圖中，最壞情況運(yùn)行時(shí)間為@(JlJEI)；在存在源點(diǎn)可達(dá)負(fù)圈的有向圖中，算法將無(wú)限運(yùn)行下去。對(duì)此，給出了改進(jìn)的SP
2、FA算法，對(duì)于任意的有向圖，該算法能夠在0(IIIEI)內(nèi)運(yùn)行完畢。最后，從實(shí)際運(yùn)行角度將SPFA算法與其它思想上同源的最短路徑算法進(jìn)行了一系列比較。關(guān)鍵詞組合算法，單源最短路徑，SPFA算法，Bellman-Ford算法中圖法分類號(hào)TP312文獻(xiàn)標(biāo)識(shí)碼AAnalysisandImprovementofSPFAAlgorithmXIAZheng-dongBUTian-mingZHANGJu-yang(ShanghaiKeyLaboratoryofTrustworthyComputing，EastChinaNormalUniversity，S}mnghai200062，China
3、)AbstractSPFA(ShortestPathFasterAlgorithm)algorithmisakindofsingle-sourceshortestpathalgorithmfordi—graphs．Becauseitseasyimplementationandgoodperformance。SPFAhasalargeinfluenceintheDomestic．Butunfor—tunately，itlacksofcorrecttheoretiealanal~is．Thispaperanalysedthisalgorithmbothintheoreticalan
4、dexperimenta1．Thepaperpointedoutthattheworst-caserunningtimeofsPFAalgorithmis@(IlIEI)inthecaseofdigraphswithnonegative-weightcyclereachablefromthesource．Inthecaseofdigraphswithnegative-weightcyclereachablefromthesource，thealgorithmwillrunindefinitely．ThispaperthenrevisesdthealgorithmSOthatit
5、is0(1IlEI)foranydigraphs．Finally，thispapercomparedSPFAinexperimentwithothershortestpathalgorithmswhicharebasedontheS&ITteidea．KeywordsCombinationalalgorithm，Single-sourceshortestpaths，SPFAalgorithm，Bellman-Fordalgorithm3．nag[v]；fa1se；1概述4．d[s]一O；最短路徑問(wèn)題是一個(gè)經(jīng)典的組合算法問(wèn)題，有著重要的5．Q一{s}；實(shí)用價(jià)值和理論意義，現(xiàn)有的各
6、種導(dǎo)航系統(tǒng)背后的核心算法6．flag[s]=true；就是最短路徑算法。到目前為止，針對(duì)各種各樣具體場(chǎng)景下7．WHILE(Q：~)8．u=QDEQUEUE()；的最短路徑算法有幾十種。文獻(xiàn)[2]中介紹了一些經(jīng)典的最9．flag[u]~false；短路徑算法，例如Dijkstra算法、Bellman-Ford算法、Pape-Levit算法、Pallottino算法、Threshold算法等，并從實(shí)驗(yàn)的角10．FOREACHvEAdj[u]u．IFd[v]>d[u]+(1，(u，v)度進(jìn)行了分析比較。12．d[v]=d[u]+∞(u，v)；1994年，西南交通大學(xué)的段凡丁提出了SP
7、FA算法l3．IFflag[v]~=false(ShortestPathFasterAlgorithm)_1]。該算法本質(zhì)上是Bell—l4．QENQUEUE(v)；man-Ford算法的一個(gè)“隊(duì)列”實(shí)現(xiàn)，其主要思想是用FIFO隊(duì)15．~lag[v]=true；列保存被松弛的結(jié)點(diǎn)，并且不斷迭代以求得最短路徑。16．returnd：SPFA的偽代碼如下：它的具體執(zhí)行過(guò)程如下：第1—3行進(jìn)行初始化，其中算法1SPFAflag是一個(gè)長(zhǎng)度為JI的數(shù)組，用來(lái)標(biāo)記節(jié)點(diǎn)是否在隊(duì)列中；輸入：有向圖G，源點(diǎn)S
