Loading...
Please wait, while we are loading the content...
Similar Documents
Accelerating Johnson ' s All-Pairs Shortest Paths Algorithm on GPU Conference
| Content Provider | Semantic Scholar |
|---|---|
| Author | Taştan, Oğuzhan Eryüksel, Oğul Can Temizel, Alptekin |
| Copyright Year | 2017 |
| Abstract | 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 allpairs shortest path calculation for large graphs with respect to the CPU. The source code is publicly available at https://github.com/ouzan19/JohnsonAlgoCUDA . . Keywords— CUDA, GPU, Johnson’s Algorithm, APSP, Parallel Processing. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://blog.asarkar.org/assets/docs/algorithms-curated/Accelerating%20Johnson's%20APSP%20Algorithm%20on%20GPU.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
