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

Abstract

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.

Keywords

• shortest paths algorithm
• blocked algorithm
• graph clustering
• single-thread application
• multi-threaded application
• speedup