Blocked algorithm of shortest paths search in sparse graphs partitioned into unequally sized clusters

Abstract

In this paper we consider the problem of searching shortest paths between all pairs of vertices of a directed weighted sparse graph which is partitioned into clusters by finding dense weakly connected subgraphs. We address this problem by developing new block-based algorithms that describe the shortest paths by matrices of blocks of unequal sizes corresponding to the sizes of the graph clusters. These algorithms extend the capabilities of known existing algorithms using blocks of equal size (such as the blocked algorithms of Floyd-Warshall family) with respect to adequate graph modeling of real networks of dif erent purposes, and with respect to ef icient use of parallelism and computational resources of multiprocessor systems and multi-core processors. The blocked algorithm of finding shortest paths in sparse large size graphs partitioned into clusters that is proposed in this paper reduces, on the one hand, the amount of memory used, and, on the other hand, reduces the number of block recalculations. Diagonal blocks describe shortest paths within clusters, non-diagonal compact blocks describe non numerous weighted arcs connecting clusters. Shortest paths between vertices of dif erent clusters are computed in real time. The memory consumption is reduced compared to the Floyd-Warshall algorithm to a number of times equal to the number of clusters. In order to reduce the number of block recalculations, a new operation is introduced to accurately compute the shortest path between vertices of one cluster, passing through the vertices and edges of another cluster, as well as through the edges connecting the clusters. Applying this operation alone allows us to find solutions that introduce a small error (a few percent) in the lengths of the shortest paths when the weights of edges between clusters are small, and allows us to find exact solutions when the weights of these edges are increased. Accurate solutions can be obtained for sparse graphs modeling road, computer, and other networks.