Heterogeneous blocked all-pairs shortest paths algorithm for clustered weighted graphs

Authors

  • Anatoly A. Prihozhy Belarusian National Technical University, 65 Niezaliezhnasci Avenue, Minsk 220013, Belarus
  • Oleg N. Karasik ISsoft Solutions, 5 Chapajeva Street, Minsk 220034, Belarus

Keywords:

clustered weighted large graph, all-pairs shortest paths, blocked algorithm, heterogeneous computations, speedup

Abstract

New heterogeneous blocked algorithm of finding all-pairs shortest paths in a large directed weighted simple graph consisting of weakly connected dense clusters (subgraphs) of different sizes is proposed. The algorithm considers and actively exploits the input and output bridge-vertices and edges of each cluster to speed up computation and localise memory accesses. It divides all blocks of the cost adjacent matrix into four types (square diagonal, rectangular vertical cross, rectangular horizontal cross and rectangular peripheral) and uses a separate computation procedure for each type, considering the design features of the block itself and the way it is computed through other blocks. A theoretical justification of the advantages of the proposed algorithms, which reduce the execution time when searching for the shortest paths, is given. The validity of the formulated statements is also confirmed by the results of computational experiments. We have developed single-threaded implementations and multi-threaded OpenMP implementations of the proposed heterogeneous algorithm and two known homogeneous blocked algorithms of finding shortest paths. Computational experiments on multicore processors were performed on directed weighted random sparse graphs decomposed into weakly connected dense clusters of different sizes. The results are described for four clustered graphs, two of which have 4800 vertices (20 and 41 clusters, respectively) and two of which have 9600 vertices (40 and 80 clusters, respectively). On the MacBook M1 Max computer in the case of single-threaded implementations proposed heterogeneous blocked algorithm for clustered graph with bridge-vertices outperformed the known homogeneous blocked algorithm for the same graphs by a factor of 1.62–1.94; in the case of multi-threaded OpenMP implementations the speedup was 1.87–1.97. On a server with Intel Xeon E5-2620v4 processors heterogeneous algorithm outperformed the known homogeneous algorithm by a factor of 1.58 –1.66 for single-threaded implementations and by a factor of 1.29–1.64 for multi-threaded implementations. A comparison of proposed algorithm with the classical blocked Floyd – Warshall algorithm in which all blocks are of the same size showed a speedup of 4.17– 8.18 times in the case of single-threaded implementations and a speedup of 3.91– 6.36 times in the case of multi-threaded OpenMP implementations.

Author Biographies

  • Anatoly A. Prihozhy, Belarusian National Technical University, 65 Niezaliezhnasci Avenue, Minsk 220013, Belarus

    doctor of science (engineering), full professor; professor at the department of software of information systems and technologies, faculty of information technology and robotics

  • Oleg N. Karasik, ISsoft Solutions, 5 Chapajeva Street, Minsk 220034, Belarus

    PhD (engineering); leading engineer

References

  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.

Downloads

Published

2026-01-04

Issue

No. 3 (2025): Journal of the Belarusian State University. Mathematics and Informatics

Section

Theoretical Foundations of Computer Science

License

Copyright (c) 2026 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)

How to Cite

[1]
Prihozhy, A.A. and Karasik, O.N. 2026. Heterogeneous blocked all-pairs shortest paths algorithm for clustered weighted graphs. Journal of the Belarusian State University. Mathematics and Informatics. 3 (Jan. 2026), 62–75.