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

关键词：桶结构 单源最短路径 dijkstra算法 bfm算法 

单位：华南理工大学电子与信息学院 广东广州510640 东莞理工学院城市学院计算机系 广东东莞523106 惠州学院教育技术中心 广东惠州516007