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

Improved SPFA Algorithm Based on Layered Graph

作　　者：沈海澜[1] 王玉斌[1] 陈再良[1] 曹子文[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机工程》2012年第13期251-253,共3页Computer Engineering

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

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]