Competing all-pairs shortest paths algorithms for sparse / dense graphs: implementation and comparison

In this paper we consider two families of competing algorithms for finding the shortest paths between all pairs of vertices (APSP) in directed weighted large graphs with different edge densities: Dijkstra and Floyd-Warshall. For comparison, we have taken Dijkstra's algorithm with dynamically varying binary heap, which solves the APSP problem purely in parallel by repeatedly executing on all vertices of the graph considered as source vertices, and we have taken blocked Floyd-Warshall algorithm, which is also well-parallelizable. It is known that in terms of computational complexity, the first algorithm is preferable on sparse graphs and the second algorithm is preferable on dense graphs. At the same time, it is not clear what are the ranges of graph densities at which the first algorithm will consume less CPU time than the second algorithm. This paper describes multithreaded implementations of parallel algorithms on multicore processors that make different usage of synchronization primitives such as mutex, conditional variable, locking, and atomic operation. By conducting computational experiments on an 8-core Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz, we found that each algorithm has a preferred graph density. In the case of multithreaded parallel implementation, the blocked Floyd-Warshall algorithm has lower running time than Dijkstra's algorithm if the graph density is greater than 0.5. Otherwise, Dijkstra's algorithm runs faster. In the case of single-threaded implementation, the split point is 0.43.

sparse graph, dense graph, APSP problem, Dijkstra-family algorithms, Floyd-Warshall family algorithms, multi-core processor, muti-threaded implementation, comparison

1. 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.

2. Dijkstra E.W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, vol. 1, no. 1, pp. 269-271.

3. Bellman R.E. On a routing problem. Quarterly of Applied Mathematics, 1958, vol. 16, no. 1, pp. 87-90.

4. Johnson D.B. Efficient Algorithms for Shortest Paths in Sparse Networks. J. ACM, 1977, vol. 24 no. 1, pp. 1-13.

5. Harish P., Narayanan P.J. Accelerating large graph algorithms on the GPU using CUDA. International conference on high-performance computing. Springer, 2007, pp. 197-208.

6. Floyd R.W. Algorithm 97: Shortest path. Communications of the ACM, 1962, no. 5 (6), p. 345.

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. 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.

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

10. 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.

11. Yang S., Liu X., Wang Y., He X., Tan G. Fast All-Pairs Shortest Paths Algorithm in Large Sparse Graph. ICS '23: Proceedings of the 37th International Conference on Supercomputing, 2023, pp. 277-288.

12. Prihozhy А.А., Karasik O.N. Advanced heterogeneous block-parallel all-pairs shortest path algorithm. Proceedings of BSTU, issue 3, Physics and Mathematics. Informatics, 2023, no. 1 (266), pp. 77-83.

13. Prihozhy A.A., Karasik O.N. 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.

14. Karasik O.N., Prihozhy A.A. Blocked algorithm of finding all-pairs shortest paths in graphs divided into weakly connected clusters. System analysis and applied information science, 2024, no. 2, pp. 4-10.

15. 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.

16. 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.

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.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.

19. Prihozhy A.A. Simulation of direct mapped, k-way and fully associative cache on all-pairs shortest paths algorithms. System analysis and applied information science, 2019, no. 4, pp. 10-18.

20. Prihozhy A.A., Karasik O.N. Influence of shortest path algorithms on energy consumption of multi-core processors. System analysis and applied information science, 2023, no. 2, pp. 4-12.