摘要： 针对数据结构课程教学中顶点数受限的最短路径问题，提出一种基于图分层的改进SPFA算法——K_SPFA。借鉴图分层思想，将原图拓展为层数与顶点限制数相等的图层，将原图中的边拓展成图层间的边。利用2个同步循环的FIFO队列和贪心策略，对SPFA算法的数据存储结构和最短路径更新操作进行改进，从而实现原图中顶点数受限的最短路径寻找。实验结果表明，K_SPFA具有较低的平均时间复杂度。

关键词: 最短路径, SPFA算法, 分层图, 同步循环, 队列, 数据结构

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

Key words: shortest path, Shortest Path Faster Algorithm(SPFA), layered graph, synchronism circulation, queue, data structure

中图分类号: 

• TP311