This article is cited in 1 paper

Applied Graph Theory

All-pairs shortest paths algorithm for high-dimensional sparse graphs

A. R. Urakov, T. V. Timeryaev

Ufa State Aviation Technical University

Abstract: All-pairs shortest path problem on weighted undirected sparse graphs is considered. “Disassembly and assembly of graph” algorithm is proposed to obtain the solution of the problem for the given graph using the solution of the problem for a small-dimensional graph. The algorithm is compared with one of the fastest classic algorithms on public source data.

Keywords: APSP, graph disassembly, graph assembly, sparse graphs.

UDC: 519.178