| 一种基于分层图的改进SPFA算法 |
| |
| 引用本文： | 沈海澜,王玉斌,陈再良,曹子文.一种基于分层图的改进SPFA算法[J].计算机工程,2012,38(13):251-253. |
| |
| 作者姓名： | 沈海澜 王玉斌 陈再良 曹子文 |
| |
| 作者单位： | 中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金资助项目，湖南省自然科学基金资助项目，中南大学信息科学与工程学院青年教师基金资助项目 |
| |
| 摘 要： | 针对数据结构课程教学中顶点数受限的最短路径问题，提出一种基于图分层的改进SPFA算法——K_SPFA。借鉴图分层思想，将原图拓展为层数与顶点限制数相等的图层，将原图中的边拓展成图层间的边。利用2个同步循环的FIFO队列和贪心策略，对SPFA算法的数据存储结构和最短路径更新操作进行改进，从而实现原图中顶点数受限的最短路径寻找。实验结果表明，K_SPFA具有较低的平均时间复杂度。
|
| 关 键 词： | 最短路径 SPFA算法 分层图 同步循环 队列 数据结构 |
| 收稿时间： | 2012-02-28 |
Improved SPFA Algorithm Based on Layered Graph |
| |
| SHEN 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. |
| |
| Authors: | SHEN Hai-lan WANG Yu-bin CHEN Zai-liang CAO Zi-wen |
| |
| Affiliation: | (School of Information Science and Engineering,Central South University,Changsha 410083,China) |
| |
| 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. |
| |
| Keywords: | shortest path Shortest Path Faster Algorithm(SPFA) layered graph synchronism circulation queue data structure |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
