Improved SPFA Algorithm Based on Layered Graph
Ziwen Cao · Jisuanji gongcheng · 2012
Aiming at the problem of vertices-constrained shortest path in data structure course teaching,this paper proposes an improved Shortest Path Faster Algorithm(SPFA) based on layered graph idea named K_SPFA.K_SPFA develops the source graph to a layered graph group and the edges in the source graph to the edges between the layered graph group.K_SPFA improves data storage structure and shortest path updating operations of SPFA with two synchronism First Input First Output(FIFO) queues and greedy technique respectively.With the improved SPFA,K_SPFA searches the shortest path of the layered graph group and accordingly gets the vertices-constrained shortest path of the source graph.Experimental results show the average time complexity of K_SPFA is lower.