关键词: 组合算法,单源最短路径,SPFA算法,Bellman-Ford算法 中图法分类号TP312文献标识码A

Abstract: 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 Θ(|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.

Key words: Combinational algorithm,Single-source shortest paths,SPFA algorithm,Bellman-Ford algorithm