Blocked algorithm of finding all-pairs shortest paths in graphs divided into weakly connected clusters

The problem of finding all shortest paths between vertices in a graph (APSP) has real-life applications in planning, communication, economics and many other areas. APSP problem can be solved using various algorithms, starting from Floyd-Warshall’s algorithm and ending with advanced, much faster blocked algorithms like Heterogeneous Blocked All-Pairs Shortest Path Algorithm designed to fully utilize underlying hardware resources and utilize inter-data relationships. In the paper, we propose a novel Blocked all-pairs Shortest Paths algorithm for Clustered Graphs (BSPCG) (in sequential and parallel forms) which utilizes the graph clustering information to significantly reduce the number of calculations by performing shortest paths search only though bridge vertices between clusters. We performed a set of comparing experiments for BSPCG and standard Blocked All-Pairs Shortest Path (BFW) algorithm on four randomly generated graphs of 4800 and 9600 vertices with different cluster configurations to determine the efficiency of calculation of paths passing through bridge vertices. All experiments were executed on a computer with two Intel Xeon E5-2620v4 processors (8 cores, 16 hardware threads and shared 20 MB L3 cache). In all the experiments the novel BSPCG algorithm outperformed the standard BFW algorithm. In single-threaded scenarios, BSPCG outperformed BFW up to 4.6 times on graphs of 4800 vertices and up to 2.7 times on graphs of 9600 vertices. In the multi-threaded scenarios, BSPCG also outperformed BFW up to times on graphs of 4800 vertices and up to 2.7 times on graphs of 9600 vertices. The proposed algorithm can be used in scenarios where clustering information stays intact or slightly modified based on the changes in graph and can be reused for future calculation of all-pairs shortest paths in the graph.

1. Schrijver A. On the history of the shortest path problem. Documenta Mathematica. 2012. Vol. 17, № 1. P. 155–167.

2. Anu P., (Kumar) M.G. Finding All-Pairs Shortest Path for a Large-Scale Transportation Network Using Parallel FloydWarshall and Parallel Dijkstra Algorithms. Journal of Computing in Civil Engineering. 2013. Vol. 27, № 3. P. 263–273.

3. Ridi L., Torrini J., Vicario E. Developing a Scheduler with Difference Matrices and the Floyd-Warshall Algorithm. IEEE Software. 2012. Vol. 29, № 1. P. 76–83.

4. E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik. 1959. Vol. 1, № 1. P. 269–271.

5. Floyd R.W. Algorithm 97: Shortest Path. Communications of the ACM. 1962. Vol. 5, № 6. P. 345-.

6. Prihozhy А., Karasik O. Inference of shortest path algorithms with spatial and temporal locality for Big Data processing. Proceedings VIII International conference “Big data and advanced analytics”, Minsk: Bestprint, 2022. P. 56-66.

7. Prihozhy A., Karasik O. Heterogenious blocked all-pairs shortest paths algorithm. System analysis and Applied Information Science. 2017. № 3. P. 68–75.

8. Venkataraman G., Sahni S., Mukhopadhyaya S. A Blocked All-Pairs Shortest Paths Algorithm. Journal of Experimental Algorithmics (JEA). 2003. Vol. 8. P. 857–874.

9. Singh A., Mishra P.K. Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm. International Journal of Computer Applications. 2014. Vol. 107, № 16. P. 23–27.

10. Karasik O., Prihozhy А. Requirements to methods of graph clustering at the aim of solving the shortest path problem. Proceedings X International conference “Big data and advanced analytics”, Minsk: BSUIR, 2024. P. 272–279.

11. Prihozhy A., Karasik O. New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes. System analysis and applied information science. BNTU, 2023. № 4. P. 4–13.

12. Prihozhy А., Karasik O. Blocked algorithm of shortest paths search in sparse graphs partitioned into unequally sized clusters. Proceedings X International conference “Big data and advanced analytics”, Minsk: BSUIR, 2024. P. 262–271.

13. Karasik O., Prihozhy A. Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation. System analysis and applied information science. BNTU, 2022. № 3. P. 57–65.

14. Karasik O., Prihozhy А. Parallel blocked all-pair shortest path algorithm: block size effect on cache operation in multicore system. Proceedings VIII International conference “Big data and advanced analytics”, Minsk: Bestprint, 2022. P. 28–38.

15. Prihozhy A., Karasik O. Influence of shortest path algorithms on energy consumption of multi-core processors. System analysis and applied information science. BNTU, 2023. № 2. P. 4–12.

16. Karasik O., Prihozhy A. Profiling of energy consumption by algorithms of shortest paths search in large dense graphs. Proceedings IX International conference “Big data and advanced analytics”, Minsk: BSUIR, 2023. P. 44–50.

17. Karasik O., Prihozhy A. Streaming block-parallel algorithm for finding shortest paths on a graph. Minsk: BSUIR 2018. № 2. P. 77–84.