We present an improved SPFA algorithm for the single source shortest path problem. For a random graph,the empirical average time complexity is O(|E|), where |E| is the number of edges of the input network.SPFA maintains a queue of candidate vertices and add a vertex to the queue only if that vertex is relaxed.In the improved SPFA, MinPoP principle is employed to improve the quality of the queue. We theoreticallyanalyse the advantage of this new algorithm and experimentally demonstrate that the algorithm is efficient.
展开▼
机译：针对单源最短路径问题，我们提出了一种改进的SPFA算法。对于随机图，经验平均时间复杂度为O（| E |），其中| E |是输入网络的边数。SPFA维护一个候选顶点队列，并且只有在该顶点放宽时才向该队列添加一个顶点。在改进的SPFA中，采用了MinPoP原理来提高队列的质量。我们从理论上分析了该新算法的优势，并通过实验证明了该算法的有效性。
展开▼
