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

摘要：

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

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

所属期刊栏目：38

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61073104;湖南省自然科学基金资助项目11JJ3067;中南大学信息科学与工程学院青年教师基金资助项目2011170314

在线出版日期：2012-10-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：251-253