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.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Parallel All-Pairs Shortest Path Algorithm: Network Decomposition Approach


    Additional title:

    Transportation Research Record: Journal of the Transportation Research Board


    Contributors:


    Publication date :

    2016-01-01




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    A Multiple Pairs Shortest Path Algorithm

    Wang, I.-L. / Johnson, E. L. / Sokol, J. S. | British Library Online Contents | 2005


    A Multiple Pairs Shortest Path Algorithm

    Wang, I.-Lin | Online Contents | 2005


    Shortest path using detour heuristic algorithm

    Wu, Shu-Hui / Wang, Shu-Jen / Tai, Chien-Ting et al. | Tema Archive | 1999


    A directionally oriented shortest path algorithm

    Butas, Larry F. | Elsevier | 1968