Accelerating Johnson’s All-Pairs Shortest Paths Algorithm on GPU

2017-09-15
Taştan, Oğuzhan
Eryüksel, Oğul Can
Temizel, Alptekin
In graph theory finding shortest paths from each node to all the others is a common problem, known as all-pairs shortest path (APSP). However, it is challenging to process large graphs containing hundreds of thousands nodes and vertices in feasible time for real world applications. In this paper, we present a parallel implementation of Johnson's algorithm, which solves APSP problem on recent GPU architecture. Proposed algorithmic and architectural optimizations results in more than 4.5 times speed up of all-pairs shortest path calculation for large graphs with respect to the CPU. The source code is publicly available at
Citation Formats
O. Taştan, O. C. Eryüksel, and A. Temizel, “Accelerating Johnson’s All-Pairs Shortest Paths Algorithm on GPU,” presented at the Accelerating Johnson’s All-Pairs Shortest Paths Algorithm on GPU”, Ulusal Yüksek Başarımlı Hesaplama Konferansı, Türkiye, 14 - 15 Eylül 2017, Türkiye, 2017, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/82701.