Heterogeneous blocked all-pairs shortest paths algorithm for clustered weighted graphs - Prihozhy, Anatoly A.; Karasik, Oleg N. (Journal of the Belarusian State University. Mathematics and Informatics, 2026)
New heterogeneous blocked algorithm of finding all-pairs shortest paths in a large directed weighted simple graph consisting of weakly connected dense clusters (subgraphs) of different sizes is proposed. The algorithm considers and actively exploits the input and output bridge-vertices and edges of each cluster to speed up computation and localise memory accesses. It divides all blocks of the cost adjacent matrix into four types (square diagonal, rectangular vertical cross, rectangular horizontal cross and rectangular peripheral) and uses a separate computation procedure for each type, considering the design features of the block itself and the way it is computed through other blocks. A theoretical justification of the advantages of the proposed algorithms, which reduce the execution time when searching for the shortest paths, is given. The validity of the formulated statements is also confirmed by the results of computational experiments. We have developed single-threaded implementations and multi-threaded OpenMP implementations of the proposed heterogeneous algorithm and two known homogeneous blocked algorithms of finding shortest paths. Computational experiments on multicore processors were performed on directed weighted random sparse graphs decomposed into weakly connected dense clusters of different sizes. The results are described for four clustered graphs, two of which have 4800 vertices (20 and 41 clusters, respectively) and two of which have 9600 vertices (40 and 80 clusters, respectively). On the MacBook M1 Max computer in the case of single-threaded implementations proposed heterogeneous blocked algorithm for clustered graph with bridge-vertices outperformed the known homogeneous blocked algorithm for the same graphs by a factor of 1.62–1.94; in the case of multi-threaded OpenMP implementations the speedup was 1.87–1.97. On a server with Intel Xeon E5-2620v4 processors heterogeneous algorithm outperformed the known homogeneous algorithm by a factor of 1.58 –1.66 for single-threaded implementations and by a factor of 1.29–1.64 for multi-threaded implementations. A comparison of proposed algorithm with the classical blocked Floyd – Warshall algorithm in which all blocks are of the same size showed a speedup of 4.17– 8.18 times in the case of single-threaded implementations and a speedup of 3.91– 6.36 times in the case of multi-threaded OpenMP implementations.