SPFA算法的分析及改进-论文.pdf

《SPFA算法的分析及改进-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第6期计算机科学Vo1．41No．62014年6月ComputerScienceJune2014SPFA算法的分析及改进夏正冬b天明张居阳(华东师范大学上海市可信重点实验室上海200062)摘要SPFA(ShortestPathFasterAlgorithm)算法是一种对任意有向图求单源最短路径的算法。该算法实现简单，实际运行效果较好，在国内有着比较大的影响力。但遗憾的是，该算法一直缺少正确的理论分析。对该算法进行了分析，指出该算法在不存在源点可达负圈的有向图中，最坏情况运行时间为@(JlJEI)；在存在源点可达负圈的有向图中，算法将无限运行下去。对此，给出了改进的SP

2、FA算法，对于任意的有向图，该算法能够在0(IIIEI)内运行完毕。最后，从实际运行角度将SPFA算法与其它思想上同源的最短路径算法进行了一系列比较。关键词组合算法，单源最短路径，SPFA算法，Bellman-Ford算法中图法分类号TP312文献标识码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；最短路径问题是一个经典的组合算法问题，有着重要的5．Q一{s}；实用价值和理论意义，现有的各

6、种导航系统背后的核心算法6．flag[s]=true；就是最短路径算法。到目前为止，针对各种各样具体场景下7．WHILE(Q：~)8．u=QDEQUEUE()；的最短路径算法有几十种。文献[2]中介绍了一些经典的最9．flag[u]~false；短路径算法，例如Dijkstra算法、Bellman-Ford算法、Pape-Levit算法、Pallottino算法、Threshold算法等，并从实验的角10．FOREACHvEAdj[u]u．IFd[v]>d[u]+(1，(u，v)度进行了分析比较。12．d[v]=d[u]+∞(u，v)；1994年，西南交通大学的段凡丁提出了SP

7、FA算法l3．IFflag[v]~=false(ShortestPathFasterAlgorithm)_1]。该算法本质上是Bell—l4．QENQUEUE(v)；man-Ford算法的一个“队列”实现，其主要思想是用FIFO队15．~lag[v]=true；列保存被松弛的结点，并且不断迭代以求得最短路径。16．returnd：SPFA的伪代码如下：它的具体执行过程如下：第1—3行进行初始化，其中算法1SPFAflag是一个长度为JI的数组，用来标记节点是否在队列中；输入：有向图G，源点S