Paralelização do Algoritmo de Dijkstra para Grafos não Direcionados de Grande Escala
DOI:
https://doi.org/10.5753/reic.2026.7147Keywords:
Computação Paralela, Caminho Mínimo, Dijkstra, OpenMP, MPI, CUDAAbstract
A escolha de uma implementação eficiente do algoritmo de Dijkstra para encontrar o caminho mais curto em grafos é crucial, especialmente em aplicações que lidam com grandes volumes de dados, como redes de transporte, sistemas de navegação e redes de telecomunicações. Este estudo investiga e compara diferentes abordagens paralelas do algoritmo de Dijkstra, incluindo implementações com OpenMP, MPI e CUDA, em relação à versão sequencial tradicional. As implementações paralelas foram avaliadas quanto ao tempo de execução, speedup e eficiência, utilizando grafos de diferentes tamanhos. Todas as versões paralelas superaram a implementação sequencial em desempenho, com variações de eficiência conforme a abordagem e o tamanho do grafo, alcançando speedup de 6,31 com 8 threads em OpenMP, 6,64 com 4 processos em MPI e 37,8 em GPU para grafos com 16.384 vértices.
Downloads
Referências
Awari, R. (2017). Parallelization of shortest path algorithm using openmp and mpi. In 2017 International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud) (I-SMAC), pages 304–309. DOI: 10.1109/I-SMAC.2017.8058360.
Backes, A. R. (2016). Estrutura de dados descomplicada: em linguagem C. GEN LTC, Rio de Janeiro.
Calderon, S., Rucci, E., and Chichizola, F. (2024). Enhanced openmp algorithm to compute all-pairs shortest path on x86 architectures. In arXiv preprint arXiv:2403.18619. DOI: 10.48550/arXiv.2403.18619.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2002). Introduction to Algorithms. MIT Press.
Farber, R. (2011). CUDA: Application Design and Development. Morgan Kaufmann, Burlington, MA.
Hassoun, M. H. and Sanghvi, A. J. (1990). Fast computation of optimal paths in two- and higher-dimension maps. Neural Networks, 3(3):355–363. DOI: 10.1016/0893-6080(90)90078-Y.
Noto, M. and Sato, H. (2000). A method for the shortest path search by extended dijkstra algorithm. In Smc 2000 conference proceedings. 2000 ieee international conference on systems, man and cybernetics. ’cybernetics evolving to systems, humans, organizations, and their complex interactions’ (cat. no.0, volume 3, pages 2316–2320. DOI: 10.1109/ICSMC.2000.886462.
NVIDIA Corporation (2023). CUDA C++ Programming Guide, Version 12.2. NVIDIA Corporation. Disponível em: [link].
OpenMP Architecture Review Board (1997). Openmp: A proposed industry standard API for shared memory programming. Technical report, OpenMP Architecture Review Board. OpenMP Fortran Application Program Interface, Version 1.0.
Sardar, T. H. and Faizabadi, A. R. (2018). Parallelization and analysis of selected numerical algorithms using openmp and pluto on symmetric multiprocessing machine. Data Technologies and Applications, 53(1):20–32. DOI: 10.1108/DTA-05-2018-0040.
Silva, G. P., Bianchini, C. P., and Costa, E. B. (2022). Programação paralela e distribuída: com MPI, OpenMP e OpenACC para computação de alto desempenho. Casa do Código, São Paulo.
Solka, J. L., Perry, J. C., Poellinger, B. R., and Rogers, G. W. (1995). Fast computation of optimal paths using a parallel dijkstra algorithm with embedded constraints. Neurocomputing, 8(2):195–212. DOI: 10.1016/0925-2312(94)00018-N.
Song, B. (2025). High-performance parallelization of dijkstra’s algorithm using mpi and cuda. arXiv preprint arXiv:2504.03667. DOI: 10.48550/arXiv.2504.03667.
Downloads
Published
Como Citar
Issue
Section
Licença
Copyright (c) 2026 Os autores
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
