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

摘要

A multi-thread parallel Single-source Shortest Path(SSSP) algorithm is proposed in multi-cores platform. It employs buckets to sort and uses the similar parallel strategy of A-Stepping algorithm. It does edge relaxations of the same bucket in parallel by slave threads, and searches all buckets in sequence by master thread. Experimental results show that this algorithm performs 4 seconds in the USA road network, achieving a higher speedup compared with serial parallel algorithm using same code.%提出一种多核平台并行单源最短路径算法.采用与Δ-Stepping算法相似的并行策略,通过多个子线程对同一个桶中的弧段进行并行松弛,利用主线程控制串行搜索中桶的序列.实验结果表明,该算法求解全美单源最短路径的时间约为4 s,与使用相同代码实现的串行算法相比,加速比更高.