多核平台并行单源最短路径算法

摘要：

提出一种多核平台并行单源最短路径算法.采用与Δ-Stepping算法相似的并行策略,通过多个子线程对同一个桶中的弧段进行并行松弛,利用主线程控制串行搜索中桶的序列.实验结果表明,该算法求解全美单源最短路径的时间约为4 s,与使用相同代码实现的串行算法相比,加速比更高.

关键词：并行算法、最短路径、网络分析、多核平台

所属期刊栏目：38

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家“863”计划基金资助项目2009AA12Z331

在线出版日期：2012-06-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：1-3