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

Abstract

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 prob-lem 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, lock-ing, 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 multi-threaded parallel imple-mentation, the blocked Floyd-Warshall algorithm has lower running time than Dijkstra's algorithm if the graph densi-ty is greater than 0.5. Otherwise, Dijkstra's algorithm runs faster. In the case of single-threaded implementation, the split point is 0.43.