一种基于分层图的改进SPFA算法

• 作者: 曹子文 沈海澜 王玉斌 陈再良
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 最短路径 SPFA算法 分层图 同步循环 队列 数据结构
• 年，卷（期）: 2012,（13）
• 所属期刊栏目: 开发研究与设计技术
• 页码范围: 251-253
• 分类号: TP311
• 字数: 5143字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2012.13.075

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈再良	中南大学信息科学与工程学院	25	212	8.0	13.0
2	沈海澜	中南大学信息科学与工程学院	25	131	7.0	10.0
3	王玉斌	中南大学信息科学与工程学院	3	17	2.0	3.0
4	曹子文	中南大学信息科学与工程学院	1	14	1.0	1.0