The all-pairs shortest path algorithms compute the shortest paths between all node pairs in a network. This paper presents a parallel algorithm for the all-pairs shortest path problem with a network decomposition approach. The algorithm decomposes the network into a set of independent augmented directed acyclic subnetworks that can be efficiently processed in parallel. The shortest path computation for each subnetwork provides a subset of the all-pairs shortest paths in the original network. The superiority of the new algorithm was verified through comparing its performance against that of the parallel single-origin shortest path algorithm. The execution times were compared for hypothetical and real-world networks with different sizes. A percentage of improvement in the execution time of about 50% was recorded for the transportation network of a large metropolitan area.
Parallel All-Pairs Shortest Path Algorithm: Network Decomposition Approach
Transportation Research Record: Journal of the Transportation Research Board
Transportation Research Record: Journal of the Transportation Research Board ; 2567 , 1 ; 95-104
01.01.2016
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
A Multiple Pairs Shortest Path Algorithm
British Library Online Contents | 2005
|A Multiple Pairs Shortest Path Algorithm
Online Contents | 2005
|Shortest path using detour heuristic algorithm
Tema Archiv | 1999
|A directionally oriented shortest path algorithm
Elsevier | 1968
|