摘要: 针对数据结构课程教学中顶点数受限的最短路径问题,提出一种基于图分层的改进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
中图分类号:
沈海澜, 王玉斌, 陈再良, 曹子文. 一种基于分层图的改进SPFA算法[J]. 计算机工程, 2012, 38(13): 251-253.
CHEN Hai-Lan, WANG Yu-Bin, CHEN Zai-Liang, CAO Zi-Wen. Improved SPFA Algorithm Based on Layered Graph[J]. Computer Engineering, 2012, 38(13): 251-253.