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.


    Zugriff

    Download

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Parallel All-Pairs Shortest Path Algorithm: Network Decomposition Approach


    Weitere Titelangaben:

    Transportation Research Record: Journal of the Transportation Research Board


    Beteiligte:


    Erscheinungsdatum :

    01.01.2016




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    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 Archiv | 1999


    A directionally oriented shortest path algorithm

    Butas, Larry F. | Elsevier | 1968