ntvНаучно-технический вестник информационных технологий, механики и оптикиScientific and Technical Journal of Information Technologies, Mechanics and Optics2226-14942500-0373Университет ИТМО10.17586/2226-1494-2025-25-5-866-875ntv-516Research ArticleКОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИCOMPUTER SCIENCEУскорение и анализ производительности алгоритмов поиска кратчайшего пути на GPU с использованием платформы CUDA: алгоритмы Беллмана–Форда, Дейкстры и Флойда–УоршеллаAccelerating and analyzing performance of shortest path algorithms on GPU using CUDA platform: Bellman-Ford, Dijkstra, and Floyd-Warshall algorithmshttps://orcid.org/0009-0009-4173-2447БодраД.BodraD.

Бодра Дип — магистр, студент, Гаррисбергский университет науки и технологий

sc 57216618940

Гаррисберг, 17101

Deep Bodra — Magister, Student

sc 57216618940

Harrisburg,17101

Deepbodra97@gmail.comhttps://orcid.org/0009-0006-5192-0175ХайрнарС.KhairnarS.

Хайрнар Сушил — магистр, студент

sc 57204777066

Вирджиния, 24061

Sushil Khairnar — Magister, Student

sc 57204777066

Virginia, 24061

sushilk@vt.eduГаррисбергский университет науки и технологийСоединённые Штаты АмерикиHarrisburg University of Science and TechnologyUnited StatesТехнологический институт ВирджинииСоединённые Штаты АмерикиVirginia TechUnited States202527102025255866875Copyright © Бодра Д., Хайрнар С., 20252025Бодра Д., Хайрнар С.Bodra D., Khairnar S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ntv.elpub.ru/jour/article/view/516

Вычислительные требования к алгоритмам поиска кратчайшего пути на больших графах с миллионами вершин и ребер представляют собой значительную проблему для последовательных реализаций, часто требуя многочасового времени выполнения даже с помощью мощных процессоров. В работе выполнена оценка реализации на графических процессорах трех фундаментальных алгоритмов поиска кратчайшего пути: Беллмана–Форда, Дейкстры и Флойда–Уоршелла с использованием платформы NVIDIA CUDA. Проведено сравнение нескольких вариантов каждого алгоритма, от базовых параллельных подходов до специфических алгоритмов улучшения. Исследованы базовые методы оптимизации, включая циклы с шагом сетки, использование общей памяти, объединение памяти. Также выполнен анализ алгоритмов улучшения, таких как раннее завершение на основе флагов для алгоритма Беллмана–Форда и тайловые вычисления для алгоритма Флойда–Уоршелла. В исследовании представлен анализ производительности, выполнено сравнение различных стратегий оптимизации и их эффективности на различных наборах графовых данных.

The computational demands of the shortest path algorithms on large-scale graphs with millions of vertices and edges pose significant challenges for serial implementations, often requiring hours of execution time even on powerful CPUs. This paper evaluates Graphic Processing Units implementations of three fundamental shortest path algorithms — BellmanFord, Dijkstra, and Floyd-Warshall using NVIDIA CUDA platform. We implemented and compared multiple variants of each algorithm, starting with basic parallel approaches and applying various optimization techniques, including gridstride loops, shared memory utilization, memory coalescing, and algorithm-specific enhancements such as flag-based early termination for Bellman-Ford and tiled computation for Floyd-Warshall. Our study provides performance analysis comparing different optimization strategies and their effectiveness across various graph datasets.

вычисления на GPUплатформа CUDAалгоритмы поиска кратчайшего путипараллельные алгоритмыалгоритмы графовБеллман–ФордДейкстраФлойд–Уоршеллоптимизация производительностиGPU computingCUDA platformshortest path algorithmsparallel algorithmsgraph algorithmsBellman-FordDijkstraFloyd-Warshallperformance optimizationReferencesHarish P., Narayanan P.J. Accelerating large graph algorithms on the GPU using CUDA. Lecture Notes in Computer Science, 2007, vol. 4873, pp. 197–208. https://doi.org/10.1007/978-3-540-77220-0_21Harish P., Narayanan P.J. Accelerating large graph algorithms on the GPU using CUDA. Lecture Notes in Computer Science, 2007, vol. 4873, pp. 197–208. https://doi.org/10.1007/978-3-540-77220-0_21Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. MIT press, 2009. 1292 p.Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. MIT press, 2009. 1292 p.Katz G.J., Kider J.T. All-pairs shortest-paths for large graphs on the GPU. Proc. of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, 2008, pp. 47–55.Katz G.J., Kider J.T. All-pairs shortest-paths for large graphs on the GPU. Proc. of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, 2008, pp. 47–55.Lebedev S.S., Novikov F.A. The Necessary and sufficient condition for Dijkstra’s algorithm applicability. Computer Tools in Education, 2017, no. 4, pp. 5–13. (in Russian)Lebedev S.S., Novikov F.A. The Necessary and sufficient condition for Dijkstra’s algorithm applicability. Computer Tools in Education, 2017, no. 4, pp. 5–13. (in Russian)Lund B., Smith J.W. A multi-stage cuda kernel for floyd-warshall. arXiv, 2010, arXiv:1001.4108. https://doi.org/10.48550/arXiv.1001.4108Lund B., Smith J.W. A multi-stage cuda kernel for floyd-warshall. arXiv, 2010, arXiv:1001.4108. https://doi.org/10.48550/arXiv.1001.4108Winkler D., Meister M., Rezavand M., Rauch W. gpuSPHASE—A shared memory caching implementation for 2D SPH using CUDA. Computer Physics Communications, 2017, vol. 213, pp. 165–180. https://doi.org/10.1016/j.cpc.2016.11.011Winkler D., Meister M., Rezavand M., Rauch W. gpuSPHASE—A shared memory caching implementation for 2D SPH using CUDA. Computer Physics Communications, 2017, vol. 213, pp. 165–180. https://doi.org/10.1016/j.cpc.2016.11.011Harris M. CUDA Pro Tip: write flexible kernels with grid-stride loops. Available at: https://developer.nvidia.com/blog/cuda-pro-tipwrite-flexible-kernels-grid-stride-loops. (accessed: 30.05.2025)Harris M. CUDA Pro Tip: write flexible kernels with grid-stride loops. Available at: https://developer.nvidia.com/blog/cuda-pro-tipwrite-flexible-kernels-grid-stride-loops. (accessed: 30.05.2025)Yang S., Liu X., Wang Y., He X., Tan G. Fast All-Pairs Shortest Paths algorithm in large sparse graph. Proc. of the 37th International Conference on Supercomputing, 2023, pp. 277–288. https://doi.org/10.1145/3577193.3593728Yang S., Liu X., Wang Y., He X., Tan G. Fast All-Pairs Shortest Paths algorithm in large sparse graph. Proc. of the 37th International Conference on Supercomputing, 2023, pp. 277–288. https://doi.org/10.1145/3577193.3593728Tang W., Chen T., Armstrong M.P. GPU-accelerated parallel all-pair shortest path routing within stochastic road networks. International Journal of Geographical Information Science, 2025, vol. 39, no. 1, pp. 53–85. https://doi.org/10.1080/13658816.2024.2394651Tang W., Chen T., Armstrong M.P. GPU-accelerated parallel all-pair shortest path routing within stochastic road networks. International Journal of Geographical Information Science, 2025, vol. 39, no. 1, pp. 53–85. https://doi.org/10.1080/13658816.2024.2394651Spridon D.E., Deaconu A.M., Tayyebi J. Novel GPU-based method for the generalized maximum flow problem. Computation, 2025, vol. 13, no. 2, pp. 40. https://doi.org/10.3390/computation13020040Spridon D.E., Deaconu A.M., Tayyebi J. Novel GPU-based method for the generalized maximum flow problem. Computation, 2025, vol. 13, no. 2, pp. 40. https://doi.org/10.3390/computation13020040Agarwal P., Dutta M. New approach of Bellman Ford algorithm on GPU using compute unified design architecture (CUDA). International Journal of Computer Applications, 2015, vol. 110, no. 13, pp. 1–5. https://doi.org/10.5120/19375-1027Agarwal P., Dutta M. New approach of Bellman Ford algorithm on GPU using compute unified design architecture (CUDA). International Journal of Computer Applications, 2015, vol. 110, no. 13, pp. 1–5. https://doi.org/10.5120/19375-1027Song B. High-performance parallelization of Dijkstra’s algorithm using MPI and CUDA. arXiv, 2025, arXiv:2504.03667. https://doi.org/10.48550/arXiv.2504.03667Song B. High-performance parallelization of Dijkstra’s algorithm using MPI and CUDA. arXiv, 2025, arXiv:2504.03667. https://doi.org/10.48550/arXiv.2504.03667Bengtsson M., Wittsten J., Waidringer J. Warehouse storage and retrieval optimization via clustering, dynamic systems modeling, and GPU-accelerated routing. arXiv, 2025, arXiv:2504.20655. https://doi.org/10.48550/arXiv.2504.20655Bengtsson M., Wittsten J., Waidringer J. Warehouse storage and retrieval optimization via clustering, dynamic systems modeling, and GPU-accelerated routing. arXiv, 2025, arXiv:2504.20655. https://doi.org/10.48550/arXiv.2504.20655Kumar H.S., Singh A., Ojha M.K. Artificial intelligence based navigation in quasi structured environment. arXiv, 2024, arXiv:2407.17508. https://doi.org/10.48550/arXiv.2407.17508Kumar H.S., Singh A., Ojha M.K. Artificial intelligence based navigation in quasi structured environment. arXiv, 2024, arXiv:2407.17508. https://doi.org/10.48550/arXiv.2407.17508Morgan N., Yenusah C., Diaz A., Dunning D., Moore J., Heilman E., et al. On a simplified approach to achieve parallel performance and portability across CPU and GPU architectures. Information, 2024, vol. 15, no. 11, pp. 673. https://doi.org/10.3390/info15110673Morgan N., Yenusah C., Diaz A., Dunning D., Moore J., Heilman E., et al. On a simplified approach to achieve parallel performance and portability across CPU and GPU architectures. Information, 2024, vol. 15, no. 11, pp. 673. https://doi.org/10.3390/info15110673Leskovec J., Krevl A. SNAP Datasets: Stanford large network dataset collection. 2014. Available at: http://snap.stanford.edu/dataLeskovec J., Krevl A. SNAP Datasets: Stanford large network dataset collection. 2014. Available at: http://snap.stanford.edu/dataBuluç A., Gilbert J.R., Budak C. Solving path problems on the GPU. Parallel Computing, 2010, vol. 36, no. 5-6, pp. 241–253. https://doi.org/10.1016/j.parco.2009.12.002Buluç A., Gilbert J.R., Budak C. Solving path problems on the GPU. Parallel Computing, 2010, vol. 36, no. 5-6, pp. 241–253. https://doi.org/10.1016/j.parco.2009.12.002Merrill D., Garland M., Grimshaw A. Scalable GPU graph traversal. ACM SIGPLAN Notices, 2012, vol. 47, no. 8, pp. 117–128. https://doi.org/10.1145/2370036.2145832Merrill D., Garland M., Grimshaw A. Scalable GPU graph traversal. ACM SIGPLAN Notices, 2012, vol. 47, no. 8, pp. 117–128. https://doi.org/10.1145/2370036.2145832Kirk D.B., Hwu W.M.W. Programming Massively Parallel Processors: a Hands-on Approach. Morgan Kaufmann, 2016, 576 p.Kirk D.B., Hwu W.M.W. Programming Massively Parallel Processors: a Hands-on Approach. Morgan Kaufmann, 2016, 576 p.Nickolls J., Buck I., Garland M., Skadron K. Scalable parallel programming with CUDA. Queue, 2008, vol. 6, no. 2, pp. 40–53. https://doi.org/10.1145/1365490.1365500Nickolls J., Buck I., Garland M., Skadron K. Scalable parallel programming with CUDA. Queue, 2008, vol. 6, no. 2, pp. 40–53. https://doi.org/10.1145/1365490.1365500Bodra D., Khairnar S. Comparative performance analysis of modern NoSQL data technologies: Redis, Aerospike, and Dragonfly. Journal of Research, Innovation and Technologies, 2025, vol. 4, no. 2, pp. 193–200. https://doi.org/10.57017/jorit.v4.2(8).05Bodra D., Khairnar S. Comparative performance analysis of modern NoSQL data technologies: Redis, Aerospike, and Dragonfly. Journal of Research, Innovation and Technologies, 2025, vol. 4, no. 2, pp. 193–200. https://doi.org/10.57017/jorit.v4.2(8).05Khairnar S., Bodra D. Recommendation engine for Amazon magazine subscriptions. International Journal of Advanced Computer Science and Applications, 2025, vol. 16, no. 7, pp. 1–8. https://doi.org/10.14569/ijacsa.2025.0160796Khairnar S., Bodra D. Recommendation engine for Amazon magazine subscriptions. International Journal of Advanced Computer Science and Applications, 2025, vol. 16, no. 7, pp. 1–8. https://doi.org/10.14569/ijacsa.2025.0160796

The authors declare that there are no conflicts of interest present.