FAST SEARCH FOR SHORTEST PATHS IN LARGE SPARSE GRAPHS DIVIDED INTO CONNECTED DENSE CLUSTERS

UDC 004.4−004.9

 

Prihozhy Anatoly Alexievich − DSc (Engineering), Professor, Professor, the Department of Computer and System Software. Belarusian National Technical University (65, Nezalezhnasti Ave., 220013, Minsk, Republic of Belarus). E-mail: prihozhy@yahoo.com

Karasik Oleg Nikolayevich − PhD (Engineering), Lead Engineer, ISsoft Solutions (5, Chapaeva str., 220034, Minsk, Republic of Belarus). E-mail: karasik.oleg.nikolaevich@gmail.com

 

DOI: https://doi.org/ 10.52065/2520-6141-2024-284-13.

Key words: sparse graph, cluster, shortest paths problem, blocked algorithm, unequally sized blocks, space and time efficiency.

For citation: Prihozhy А. А., Karasik O. N. Fast search for shortest paths in large sparse graphs divided into connected dense clusters. Proceedings of BSTU, issue 3, Physics and Mathematics. Informatics, 2024, no. 2 (284), pp. 96–103. DOI: 10.52065/2520-6141-2024-284-13.

Abstract

The aim of the paper is to solve the problem of finding shortest paths between all pairs of vertices in simple directed weighted large sparse graphs. It is assumed that the graphs with positive and negative real weights of edges are decomposed into unequally sized weakly connected clusters. Since the problem has numerous practical applications in various domains, and the graphs may be too large, our goal is to speed up the problem solving on modern heterogeneous multiprocessor systems and multi-core processors. The paper extends the capabilities of existing blocked algorithms by utilizing blocks of unequal sizes. The extension supports natural graph modeling of real-world networks and allows the use of large sparse graphs divided into dense weakly connected clusters in the shortest path problems. Our approach is to compute shortest paths for all-pairs of cluster vertices represented by the cost adjacency matrix in advance, and afterward compute the shortest paths between vertices of different clusters through interconnect (bridge) edges in real time on demand. The approach is based on developing a new fast operation that accurately computes the shortest paths between vertices of one cluster that pass through the vertices of another neighboring cluster and through the edges connecting the clusters. Applying this operation to pairs of clusters allowed us to develop an approximate parallelizable algorithm, efficient regarding the CPU time and memory space consumed, that computes the shortest paths between the vertices within clusters and then between clusters. The algorithm can introduce inaccuracies in shortest paths when the weights of edges connecting clusters are small. It finds accurate solutions when the weights of these edges are larger than the weights of edges within clusters, e. g., in the case of road networks.

Download

References

  1. Dijkstra E. W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, vol. 1, no. 1, pp. 269–271.
  2. Floyd R.W. Algorithm 97: Shortest path. Communications of the ACM, 1962, no. 5 (6), p. 345.
  3. Glabowski M., Musznicki B., Nowak P. and Zwierzykowski P. Review and Performance Analysis of Shortest Path Problem Solving Algorithms. International Journal on Advances in Software, 2014, vol. 7, no. 1&2, pp. 20–30.
  4. Madkour A., Aref W. G., Rehman F. U., Rahman M. A., Basalamah S. A Survey of Shortest-Path Algorithms. ArXiv: 1705.02044v1 [cs. DS], 4 May 2017. 26 p.
  5. Venkataraman G., Sahni S., Mukhopadhyaya S. A Blocked All-Pairs Shortest Paths Algorithm. Journal of Experimental Algorithmics (JEA), 2003, vol. 8, pp. 857–874.
  6. Park J. S., Penner M., and Prasanna V. K. Optimizing graph algorithms for improved cache performance. IEEE Trans. on Parallel and Distributed Systems, 2004, no. 15 (9), pp. 769–782.
  7. Katz G. J., Kider J. T. All-pairs shortest-paths for large graphs on the GPU. GH’08: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, ACM, 2008, pp. 47–55.
  8. Prihozhy A. A., Karasik O. N. Heterogeneous blocked all-pairs shortest paths algorithm. Sistemnyy Analiz i prikladnaya informatika [System analysis and applied information science], 2017, no. 3, pp. 68–75. (In Russian).
  9. Prihozhy А. А., Karasik O. N. Advanced heterogeneous block-parallel all-pairs shortest path algorithm. Trudy BGTU Proceedings of BSTU, issue 3, Physics and Mathematics. Informatics, 2023, no. 1 (266), pp. 77–83.
  10. Prihozhy А. A., Karasik O. N. Inference of shortest path algorithms with spatial and temporal locality for big data processing. Big Data and Advanced Analytics: proceedings of VIII International conference. Minsk, Bestprint Publ., 2022, pp. 56–66.
  11. Prihozhy A., Karasik O. New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes. System analysis and applied information science, 2023, no. 4, pp. 4–13.
  12. Djidjev H., Thulasidasan S., Chapuis G., Andonov R. and Lavenier D. Efficient multi-GPU computation of all-pairs shortest paths. IEEE 28th International Parallel and Distributed Processing Symposium. IEEE, 2014, pp. 360–369.
  13. Yang S. Liu X., Wang Y., He X., Tan G. Fast All-Pairs Shortest Paths Algorithm in Large Sparse Graph. ICS’23 Proceedings of 37th International conference on Supercomputing, 2023, pp. 277–288.
  14. Prihozhy A. A. Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms. System analysis and applied information science, 2021, no. 3, pp. 40–50.
  15. Karasik O. N., Prihozhy A. A. Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation. System analysis and applied information science, 2022, no. 3, pp. 57–65.
  16. Prihozhy A. A., Karasik O. N. Influence of shortest path algorithms on energy consumption of multicore processors. System analysis and applied information science, 2023, no. 2, pp. 4–12.
  17. Prihozhy A. A. Generation of shortest path search dataflow networks of actors for parallel multicore implementation. Informatics, 2023, vol. 20, no. 2, pp. 65−84.
  18. Prihozhy A., Merdjani R., Iskandar F. Automatic Parallelization of Net Algorithms. Proceedings of the International Conference on Parallel Computing in Electrical Engineering (PARELEC’00). Quebec, Canada, 2000, pp. 24–28.

15.03.2024