Fast search for shortest paths in large sparse graphs divided into connected dense clusters

Abstract

The aim of the paper is to solve the problem of finding shortest paths between all pairs of vertices in simple directed weighted large sparse graphs. It is assumed that the graphs with positive and negative real weights of edges are decomposed into unequally sized weakly connected clusters. Since the problem has numerous practical applications in various domains, and the graphs may be too large, our goal is to speed up the problem solving on modern heterogeneous multiprocessor systems and multi-core processors. The paper extends the capabilities of existing blocked algorithms by utilizing blocks of unequal sizes. The extension supports natural graph modeling of real-world networks and allows the use of large sparse graphs divided into dense weakly connected clusters in the shortest path problems. Our approach is to compute shortest paths for all-pairs of cluster vertices represented by the cost adjacency matrix in advance, and afterward compute the shortest paths between vertices of different clusters through interconnect (bridge) edges in real time on demand. The approach is based on developing a new fast operation that accurately computes the shortest paths between vertices of one cluster that pass through the vertices of another neighboring cluster and through the edges connecting the clusters. Applying this operation to pairs of clusters allowed us to develop an approximate parallelizable algorithm, efficient regarding the CPU time and memory space consumed, that computes the shortest paths between the vertices within clusters and then between clusters. The algorithm can introduce inaccuracies in shortest paths when the weights of edges connecting clusters are small. It finds accurate solutions when the weights of these edges are larger than the weights of edges within clusters, e. g., in the case of road networks

Целью статьи является решение задачи поиска кратчайших путей между всеми парами вершин в простых ориентированных взвешенных больших разреженных графах. Предполагается, что графы с положительными и отрицательными действительными весами ребер декомпозированы на слабосвязанные кластеры разного размера. Поскольку задача имеет множество практических приложений в различных областях, а графы могут быть слишком большими, наша цель − ускорить решение задачи на современных гетерогенных многопроцессорных системах и многоядерных процессорах. В статье расширяются возможности существующих блочных алгоритмов за счет использования блоков неравных размеров. Расширение поддерживает естественное и адекватное графовое моделирование реальных сетей и позволяет использовать большие разреженные графы, разделенные на плотные слабосвязанные кластеры, при решении задач о кратчайших путях. Наш подход заключается в том, чтобы заранее вычислять кратчайшие пути для всех пар вершин кластеров, представленных матрицей стоимости-смежности, а затем по запросу определять кратчайшие пути между вершинами разных кластеров в реальном времени. Подход основан на разработке новой быстрой операции, которая точно вычисляет кратчайшие пути между вершинами одного кластера, проходящие через вершины другого соседнего кластера и через ребра, соединяющие кластеры. Применение этой операции к парам кластеров позволило нам разработать приближенный распараллеливаемый алгоритм, эффективный по потребляемым процессорному времени и объему памяти, вычисляющий кратчайшие пути внутри кластеров, а затем между кластерами. Алгоритм может вносить неточности в кратчайшие пути, когда веса ребер, соединяющих кластеры, малы. Он находит точные решения, когда веса этих ребер больше, чем веса ребер внутри кластеров, например, в случае дорожных сетей