CUDA solutions for the SSSP problem

Pedro J. Martín, Roberto Torres and Antonio Gavilanes

ICCS 2009: 9th International Conference Computational Science 2009 (New Orleans, USA). Conference Proceedings, Lecture Notes in Computer Science 5544, Springer-Verlag, pp. 904-913.


We present several algorithms that solve the single-source shortestpath problem using CUDA. We have run them on a database, composed of hundreds of large graphs represented by adjacency lists and adjacency matrices, achieving high speedups regarding a CPU implementation based on Fibonacci heaps. Concerning correctness, we outline why our solutions work, and show that a previous approach [10] is incorrect.

ICCS 2009

Donwload: Download link pdf download bibTexbibtex Publisher URLurl