Dijkstra's Algorithm: A Proposal for Parallelization in CUDA

• Sebastião V. Guimarães Neto UFSCar
• Hélio Guardia UFSCar

DOI: https://doi.org/10.5753/eradsp.2025.9575

Abstract

Este trabalho apresenta um estudo sobre a paralelização do algoritmo de Dijkstra para busca do menor caminho em grafos utilizando CUDA e analisa seu desempenho em comparação com a versão sequencial, comparando os tempos de execução e o speedup obtido.

References

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271.

Harish, P. and Narayanan, P. J. (2007). Accelerating large graph algorithms on the gpu using cuda. In Proceedings of the International Conference on High Performance Computing (HiPC), pages 197–208. Springer.

Martín, P. J., Asenjo, R., and Gavilanes, A. (2009). Cuda solutions for the sssp problem. In Bader, M., Bézard, M., Botelho, L. C. L., Inês, P. R. M., and ao M. L. M. Palma, J., editors, High Performance Computing for Computational Science – VECPAR 2008, volume 5336 of Lecture Notes in Computer Science, pages 203–216. Springer.