一种基于桶结构的单源最短路径算法

J4 ›› 2012, Vol. 34 ›› Issue (4): 77-81.

一种基于桶结构的单源最短路径算法

魏文红1，李清霞2，蔡昭权3

(1.华南理工大学电子与信息学院,广东广州 510640;2.东莞理工学院城市学院计算机系,广东东莞 523106;3.惠州学院教育技术中心,广东惠州 516007)

收稿日期:2011-11-05 修回日期:2012-02-10 出版日期:2012-04-26 发布日期:2012-04-25
基金资助:
国家青年自然科学基金资助项目（61103037）；中国博士后科学基金资助项目（20110490883）；东莞市科技计划项目（2011108102015）；惠州市科技计划项目（2011B010003003）

A SingleSource Shortest Path Algorithm Based on the Bucket Structure

WEI Wenhong1,LI Qingxia2,CAI Zhaoquan3

(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)

Received:2011-11-05 Revised:2012-02-10 Online:2012-04-26 Published:2012-04-25

摘要/Abstract

摘要：

以单源最短路径为主的最优路径问题是众多社会应用领域内选择最优问题的基础。本文分析了不同实现技术求解单源最短路径问题的算法，结合基于标记设定的Dijkstra算法和基于标记修正的BFM算法的思想，提出了一种基于桶结构的单源最短路径算法。实验结果表明，该算法与前两种算法相比，具有好的运行时间复杂度和可并行性。

关键词: 桶结构, 单源最短路径, Dijkstra算法, BFM算法

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.

Key words: bucket structure;singlesource shortest path;Dijkstra algorithm;BFM algorithm

魏文红1，李清霞2，蔡昭权3. 一种基于桶结构的单源最短路径算法[J]. J4, 2012, 34(4): 77-81.

WEI Wenhong1,LI Qingxia2,CAI Zhaoquan3. A SingleSource Shortest Path Algorithm Based on the Bucket Structure[J]. J4, 2012, 34(4): 77-81.

[1]	刘雨青, 向军, 曹守启. 基于改进蚁群算法的水下自主航行机器人路径规划[J]. 计算机工程与科学, 2022, 44(03): 536-544.
[2]	苟平章，张芬，毛刚，贾向东. 基于AGNES聚类的能耗均衡WSNs优化路由算法[J]. 计算机工程与科学, 2020, 42(04): 620-627.
[3]	刘国繁1,许多2. 基于非均匀分簇与路径优化的WSN路由协议[J]. J4, 2015, 37(08): 1492-1497.
[4]	刘建伟卢建朱张彦军. 一个改进的调配算法[J]. J4, 2007, 29(1): 73-75.
[5]	徐凤生. 求最短路径的新算法[J]. J4, 2006, 28(2): 83-85.
[6]	徐凤生李天志. 所有最短路径的求解算法[J]. J4, 2006, 28(12): 83-84.
[7]	周培德. 交通道路网中任意两点之最短路径的快速算法[J]. J4, 2002, 24(4): 35-37.