Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин кластеризованного взвешенного графа

Авторы

  • Анатолий Алексеевич Прихожий Белорусский национальный технический университет, пр. Независимости, 65, 220013, г. Минск, Беларусь
  • Олег Николаевич Карасик Иссофт Солюшенз, ул. Чапаева, 5, 220034, г. Минск, Беларусь

Ключевые слова:

кластеризованный взвешенный большой граф, кратчайшие пути между всеми парами вершин, блочный алгоритм, гетерогенные вычисления, ускорение

Аннотация

Предлагается новый гетерогенный блочный алгоритм поиска кратчайших путей между всеми парами вершин большого ориентированного взвешенного простого графа, состоящего из слабосвязанных плотных кластеров (подграфов) разных размеров. Алгоритм учитывает и активно использует входные и выходные граничные вершины и ребра каждого кластера для ускорения вычислений и локализации обращений к памяти. Он делит все блоки матрицы «стоимость – смежность» на четыре типа (квадратный диагональный, прямоугольный вертикальный на кресте, прямоугольный горизонтальный на кресте и прямоугольный периферийный) и использует отдельную процедуру расчета для них, учитывает конструктивные особенности самого блока и способ его расчета через другие блоки. Приводится теоретическое обоснование преимуществ предлагаемых алгоритмов, сокращающих время выполнения при поиске кратчайших путей. Достоверность сформулированных положений подтверждается результатами проведенных вычислительных экспериментов. Разрабатываются однопоточные реализации и многопоточные OpenMP реализации предлагаемого гетерогенного алгоритма и двух известных гомогенных блочных алгоритмов для поиска кратчайших путей. Вычислительные эксперименты на многоядерных процессорах проводятся на случайных ориентированных взвешенных графах, декомпозированных на слабосвязанные плотные кластеры разных размеров. Описываются результаты для четырех кластеризованных графов, два из которых имеют 4800 вершин (20 и 41 кластер соответственно) и два из которых имеют 9600 вершин (40 и 80 кластеров соответственно). На компьютере MacBook M1 Max в случае с однопоточностью предложенный гетерогенный блочный алгоритм для кластеризованных графов с граничными вершинами превзошел известный гомогенный блочный алгоритм для таких же графов в 1,62–1,94 раза; в случае с OpenMP-многопоточностью ускорение составило 1,87–1,97. На сервере из двух процессоров Intel Xeon E5-2620v4 гетерогенный алгоритм превзошел гомогенный алгоритм в 1,58 –1,66 раза для однопоточности и в 1,29–1,64 раза для многопоточности. Сравнение предложенного алгоритма с классическим блочным алгоритмом Флойда – Уоршелла, в котором блоки имеют одинаковый размер, показало ускорение в 4,17– 8,18 раза в случае с однопоточностью и ускорение в 3,91– 6,36 раза в случае с OpenMP-многопоточностью.

Биографии авторов

  • Анатолий Алексеевич Прихожий, Белорусский национальный технический университет, пр. Независимости, 65, 220013, г. Минск, Беларусь

    доктор технических наук, профессор; профессор кафедры программного обеспечения информационных систем и технологий факультета информационных технологий и робототехники

  • Олег Николаевич Карасик, Иссофт Солюшенз, ул. Чапаева, 5, 220034, г. Минск, Беларусь

    кандидат технических наук; ведущий инженер

Библиографические ссылки

  1. Madkour A, Aref WG, Rehman F, Rahman MA, Basalamah SM. Survey of shortest-path algorithms. arXiv:1705.02044vl [Preprint]. 2017 [cited 2025 May 2]: [26 p.]. Available from: https://arxiv.org/abs/1705.02044.
  2. Prihozhy AA. Synthesis of quantum circuits based on incompletely specified functions and if-decision diagrams. Journal of the Belarusian State University. Mathematics and Informatics. 2021;3:84–97. DOI: 10.33581/2520-6508-2021-3-84-97.
  3. Floyd RW. Algorithm 97: shortest path. Communications of the ACM. 1962;5(6):345. DOI: 10.1145/367766.368168.
  4. Warshall S. A theorem on boolean matrices. Journal of the ACM. 1962;9(1):11–12. DOI: 10.1145/321105.321107.
  5. Venkataraman GA, Sahni S, Mukhopadhyaya S. A blocked all-pairs shortest-paths algorithm. Journal of Experimental Algorithmics. 2003;8:857–874. DOI: 10.1145/996546.996553.
  6. Park J-S, Penner M, Prasanna VK. Optimizing graph algorithms for improved cache performance. IEEE Transactions on Parallel and Distributed Systems. 2004;15(9):769–782. DOI: 10.1109/TPDS.2004.44.
  7. Лиходед НА, Сипейко ДС. Обобщенный блочный алгоритм Флойда – Уоршелла. Журнал Белорусского государственного университета. Математика. Информатика. 2019;3:84–92. DOI: 10.33581/2520-6508-2019-3-84-92.
  8. Djidjev H, Chapuis G, Andonov R, Thulasidasan S, Lavenier D. All-pairs shortest path algorithms for planar graph for GPU-accelerated clusters. Journal of Parallel and Distributed Computing. 2015;85:91–103. DOI: 10.1016/j.jpdc.2015.06.008ff.
  9. Yang S, Liu X, Wang Y, He X, Tan G. Fast all-pairs shortest paths algorithm in large sparse graph. In: Association for Computing Machinery. ICS’23. Proceedings of the 37 th International conference on supercomputing; 2023 June 21–23; Orlando, USA. New York: Association for Computing Machinery; 2023. p. 277–288. DOI: 10.1145/3577193.3593728.
  10. Прихожий АА, Карасик ОН. Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин графа. Системный анализ и прикладная информатика. 2017;3:68–75. EDN: ZWMSYN.
  11. Prihozhy АА, Karasik ON. Advanced heterogeneous block-parallel all-pairs shortest path algorithm. Proceedings of BSTU. Issue 3, Physics and Mathematics. Informatics. 2023;1:77–83. DOI: 10.52065/2520-6141-2023-266-1-13.
  12. Prihozhy AA, Karasik ON. New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes. System Analysis and Applied Information Science. 2023;(4):4–13. DOI: 10.21122/2309-4923-2023-4-4-13.
  13. Prihozhy АА, Karasik ON. Blocked algorithm of shortest paths search in sparse graphs partitioned into unequally sized clusters. In: Bogush VA, Dik SK, Likhachevskii DV, Kazak TV, Piskun GA, editors. Big data and high-level analysis. Collection of scientific articles of the 10th International scientific and practical conference; 2024 March 13; Minsk, Belarus. Minsk: Belarusian State University of Informatics and Radioelectronics; 2024. p. 262–271. EDN: FSMHWS.
  14. Karasik ON, Prihozhy AA. Blocked algorithm of finding all-pairs shortest paths in graphs divided into weakly connected clusters. System Analysis and Applied Information Science. 2024;2:4–10. DOI: 10.21122/2309-4923-2024-2-4-10.
  15. Carlson T, Wong G. Optimization of the Floyd – Warshall shortest path algorithm. In: Arabnia HR, Deligiannidis L, Amirian S, Ghareh Mohammadi F, Shenavarmasouleh F, editors. Foundations of computer science and frontiers in education: computer science and computer engineering. Proceedings of the 20 th International conference on foundations of computer science and 20th International conference on frontiers in education; 2024 July 22–25; Las Vegas, USA. Las Vegas: Springer; 2025. p. 84–90 (Communications in computer and information science; volume 2261).
  16. Sangeetha DP, Sekar S, Parvathy PR, GaneshBabu SRTR, Muthulekshmi M. Optimizing shortest paths in big data using the Floyd – Warshall algorithm. In: GL BAJAJ Group of Institutions. Proceedings of the International conference on intelligent control, computing and communications; 2025 February 13–14; Mathura, India. [S. l.]: IEEE; 2025. p. 382–387. DOI: 10.1109/IC363308.2025.10957179.
  17. Liu G. Solving the all pairs shortest path problem after minor update of a large dense graph. arXiv:2412.15122v6 [Preprint]. 2025 [cited 2025 November 16]: [10 p.]. Available from: https://arxiv.org/pdf/2412.15122.
  18. Kumar S, Karthik S, Srilakshmi S, Dharun Viginesh P. Performance analysis of Floyd – Warshall algorithm: sequential and parallel execution using intel oneAPI. In: RVS Technical Campus. Proceedings of the 8 th International conference on electronics, communication and aerospace technology; 2024 August 6; Coimbatore, India. [S. l.]: IEEE; 2024. p. 205–211. DOI: 10.1109/ICECA63461.2024.10800787.
  19. Карасик ОН, Прихожий АА. Потоковый блочно-параллельный алгоритм поиска кратчайших путей на графе. Доклады Белорусского государственного университета информатики и радиоэлектроники. 2018;2:77–84. EDN: YVOTCR.
  20. Prihozhy AA. Generation of shortest path search dataflow networks of actors for parallel multi-core implementation. Informatics. 2023;20(2):65–84. DOI: 10.37661/1816-0301-2023-20-2-65-84.
  21. Karasik ON, Prihozhy AA. Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation. System Analysis and Applied Information Science. 2022;3:57–65. DOI: 10.21122/2309-4923-2022-3-57-65.
  22. Prihozhy AA, Karasik ON. Influence of shortest path algorithms on energy consumption of multi-core processors. System Analysis and Applied Information Science. 2023;2:4–12. DOI: 10.21122/2309-4923-2023-2-4-12.

Загрузки

Опубликован

2026-01-04

Выпуск

№ 3 (2025): Журнал Белорусского государственного университета. Математика. Информатика

Раздел

Теоретические основы информатики

Лицензия

Copyright (c) 2026 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).

Как цитировать

[1]
Прихожий, А.А. и Карасик, О.Н. 2026. Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин кластеризованного взвешенного графа. Журнал Белорусского государственного университета. Математика. Информатика. 3 (янв. 2026), 62–75.