SPFA算法的分析及改进

Analysis and Improvement of SPFA Algorithm

SPFA(Shortest Path Faster Algorithm)算法是一种对任意有向图求单源最短路径的算法。该算法实现简单,实际运行效果较好,在国内有着比较大的影响力。但遗憾的是,该算法一直缺少正确的理论分析。对该算法进行了分析,指出该算法在不存在源点可达负圈的有向图中,最坏情况运行时间为Θ(|V||E|);在存在源点可达负圈的有向图中,算法将无限运行下去。对此,给出了改进的SPFA算法,对于任意的有向图,该算法能够在O(|V||E|)内运行完毕。最后,从实际运行角度将SPFA算法与其它思想上同源的最短路径算法进行了一系列比较。

SPFA （Shortest Path Faster Algorithm） algorithm is a kind of single-source shortest path algorithm for digraphs.Because its easy implementation and good performance,SPFA has a large influence in the Domestic.But unfortunately,it lacks of correct theoretical analysis.This paper analysed this algorithm both in theoretical and experimental.The paper pointed out that the worst-case running time of SPFA algorithm is （O）（｜V｜ [E｜） in the case of digraphs with no negative-weight cycle reachable from the source.In the case of digraphs with negative-weight cycle reachable from the source,the algorithm will run indefinitely.This paper then revisesd the algorithm so that it is O（｜V｜｜E｜） for any digraphs.Finally,this paper compared SPFA in experiment with other shortest path algorithms which are based on the same idea.