Parallel Single-source Shortest Path Algorithm on Multi-core Platform
Ershun Zhong · Jisuanji gongcheng · 2012
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 Δ-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.