%0 Journal Article
%T spfa算法的分析及改进
%A 夏正冬？
%A 卜天明？
%A 张居阳？
%J 计算机科学
%D 2014
%R 10.11896/j.issn.1002-137X.2014.06.035
%X spfa(shortestpathfasteralgorithm)算法是一种对任意有向图求单源最短路径的算法。该算法实现简单,实际运行效果较好,在国内有着比较大的影响力。但遗憾的是,该算法一直缺少正确的理论分析。对该算法进行了分析,指出该算法在不存在源点可达负圈的有向图中,最坏情况运行时间为θ(|v||e|)；在存在源点可达负圈的有向图中,算法将无限运行下去。对此,给出了改进的spfa算法,对于任意的有向图,该算法能够在o(|v||e|)内运行完毕。最后,从实际运行角度将spfa算法与其它思想上同源的最短路径算法进行了一系列比较。
%K 组合算法
%K 单源最短路径
%K spfa算法
%K bellman-ford算法中图法分类号tp312文献标识码a
%U http://www.jsjkx.com/jsjkx/ch/reader/view_abstract.aspx?file_no=20140635&flag=1