Parallel Dijkstra’s Algorithm for Large-Scale Non-Directed Graphs
DOI:
https://doi.org/10.5753/reic.2026.7147Keywords:
Parallel Computing, Shortest Path, Dijkstra, OpenMP, MPI, CUDAAbstract
The efficient implementation of Dijkstra’s algorithm for finding the shortest path in graphs is crucial, especially in applications that handle large volumes of data, such as transportation networks, navigation systems, and telecommunication networks. This study investigates and compares different parallel approaches to Dijkstra’s algorithm, including implementations with OpenMP, MPI, and CUDA, against the traditional sequential version. The parallel implementations were evaluated in terms of execution time, speedup, and efficiency using graphs of different sizes. All parallel versions outperformed the sequential implementation, with efficiency varying by approach and graph size, achieving speedups of 6.31 with eight threads in OpenMP, 6.64 with four processes in MPI, and 37.8 on the GPU for graphs with 16,384 vertices.
Downloads
References
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
How to Cite
Issue
Section
License
Copyright (c) 2026 The authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
