|
|||||
|
|
| 一种基于桶结构的单源最短路径算法 | |
| 引用本文： | 魏文红,李清霞,蔡昭权.一种基于桶结构的单源最短路径算法[J].计算机工程与科学,2012,34(4):77-81. |
| 作者姓名： | 魏文红 李清霞 蔡昭权 |
| 作者单位： | 1. 华南理工大学电子与信息学院,广东广州,510640 2. 东莞理工学院城市学院计算机系,广东东莞,523106 3. 惠州学院教育技术中心,广东惠州,516007 |
| 基金项目： | 国家青年自然科学基金资助项目(61103037);中国博士后科学基金资助项目(20110490883);东莞市科技计划项目(2011108102015);惠州市科技计划项目(2011B010003003) |
| 摘 要： | 以单源最短路径为主的最优路径问题是众多社会应用领域内选择最优问题的基础。本文分析了不同实现技术求解单源最短路径问题的算法,结合基于标记设定的Dijkstra算法和基于标记修正的BFM算法的思想,提出了一种基于桶结构的单源最短路径算法。实验结果表明,该算法与前两种算法相比,具有好的运行时间复杂度和可并行性。 |
| 关 键 词： | 桶结构 单源最短路径 Dijkstra算法 BFM算法 |
A Single-Source Shortest Path Algorithm Based on the Bucket Structure |
|
| WEI Wen-hong , LI Qing-xia , CAI Zhao-quan.A Single-Source Shortest Path Algorithm Based on the Bucket Structure[J].Computer Engineering & Science,2012,34(4):77-81. | |
| Authors: | WEI Wen-hong LI Qing-xia CAI Zhao-quan |
| Affiliation: | 1.School of Electronics and Information Engineering,South China University of Technology,Guangzhou 510640;2.Department of Computer Science,City College,Dongguan University of Technology,Dongguan 523106;3.Educational Technology Center,Huizhou University,Huizhou 516007,China) |
| Abstract: | The single-source shortest path problem as to the main optimal routing problem is the basis of the most optimal problems in many social application areas.This paper discusses the different single-source shortest path serial algorithms in term of the implementation technique,combining the ideas of the Dijkstra algorithm based on label setting and the BFM algorithm based on label correcting,a new kind of single-source shortest path algorithm based on the bucket structure is proposed.The experiments show that the proposed algorithm has good time complexity and parallelism property compared with the two former algorithms. |
| Keywords: | bucket structure single-source shortest path Dijkstra algorithm BFM algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 | |
| 点击此处可从《计算机工程与科学》下载全文 | |
