All-Pairs Shortest Paths Algorithm for High-dimensional Sparse Graphs

2013/08/07 by Urakov, Timeryaev
Computer Science · Engineering · #05C12 #Advanced Clustering Algorithms Research #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Graph Theory and Algorithms #Optimization and Packing Problems #acm:05C12 #cs.DS #msc:05C12

paper · pdf · doi:10.48550/arxiv.1308.1568

8 pages, 3 figures, 2 tables. A more detailed text on Russian: http://www.lib.tsu.ru/mminfo/000349342/19/image/19-084.pdf

arxiv created 2013/08/07 · openalex publication_date 2013/08/07 · arxiv updated 2013/08/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Here the All-pairs shortest path problem on weighted undirected sparse graphs is being considered. For the problem considered, we propose ``disassembly and assembly of a graph'' algorithm which uses a solution of the problem on a small-dimensional graph to obtain the solution for the given graph. The proposed algorithm has been compared to one of the fastest classic algorithms on data from an open public source.

Citations

• A note on two problems in connexion with graphs

Related

• A New Fast Weighted All-pairs Shortest Path Search Algorithm Based on Pruning by Shortest Path Trees
• Solving the all pairs shortest path problem after minor update of a large dense graph
• Improving The Floyd-Warshall All Pairs Shortest Paths Algorithm
• A New Fast Unweighted All-pairs Shortest Path Search Algorithm Based on Pruning by Shortest Path Trees
• An all-pairs shortest path algorithm for bipartite graphs