spfa算法的分析及改进

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