Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
Finding All-Pairs Shortest Path for a Large-Scale Transportation Network Using Parallel Floyd-Warshall and Parallel Dijkstra Algorithms
Parallel computing has become a powerful approach for solving real-time decisions about large-scale, computing-intensive transportation problems. A frequently encountered transportation problem is the “shortest path problem;” that is, finding the shortest path between any two nodes in a transportation network. For the large transportation networks encountered in major metropolitan areas, this problem can be computationally demanding, especially if shortest paths between all the nodes in the network need to be dynamically updated (e.g., evolving traffic conditions). In such a situation, one may wish to harness parallel computing to solve this problem. However, the parallel implementations of commonly used shortest-path algorithms are computationally demanding because of the inherent sequential nature of the search process used by the algorithms. This paper describes parallel implementations and includes performance analyses of two prominent graph algorithms (i.e., Floyd-Warshall and Dijkstra) used for finding the all-pairs shortest path for a large-scale transportation network. The results indicate that a multilevel parallel implementation that combines message passing interface (MPI) with shared memory threads [e.g., Open Multiprocessing (OpenMP) or POSIX Threads (pthreads)] is effective for solving these problems on a moderate number of symmetric multiprocessor (SMP) nodes. This paper also includes the derivation of the computational time for the different parallel implementations of these two graph algorithms.
Finding All-Pairs Shortest Path for a Large-Scale Transportation Network Using Parallel Floyd-Warshall and Parallel Dijkstra Algorithms
Parallel computing has become a powerful approach for solving real-time decisions about large-scale, computing-intensive transportation problems. A frequently encountered transportation problem is the “shortest path problem;” that is, finding the shortest path between any two nodes in a transportation network. For the large transportation networks encountered in major metropolitan areas, this problem can be computationally demanding, especially if shortest paths between all the nodes in the network need to be dynamically updated (e.g., evolving traffic conditions). In such a situation, one may wish to harness parallel computing to solve this problem. However, the parallel implementations of commonly used shortest-path algorithms are computationally demanding because of the inherent sequential nature of the search process used by the algorithms. This paper describes parallel implementations and includes performance analyses of two prominent graph algorithms (i.e., Floyd-Warshall and Dijkstra) used for finding the all-pairs shortest path for a large-scale transportation network. The results indicate that a multilevel parallel implementation that combines message passing interface (MPI) with shared memory threads [e.g., Open Multiprocessing (OpenMP) or POSIX Threads (pthreads)] is effective for solving these problems on a moderate number of symmetric multiprocessor (SMP) nodes. This paper also includes the derivation of the computational time for the different parallel implementations of these two graph algorithms.
Finding All-Pairs Shortest Path for a Large-Scale Transportation Network Using Parallel Floyd-Warshall and Parallel Dijkstra Algorithms
Pradhan, Anu (Autor:in) / Mahinthakumar, G. (Kumar) (Autor:in)
Journal of Computing in Civil Engineering ; 27 ; 263-273
12.04.2012
112013-01-01 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
| British Library Online Contents | 2013
Floyd-Warshall in Scheduling Open Networks
| TIBKAT | 2016
Parallel All-Pairs Shortest Path Algorithm: Network-Decomposition Approach
| British Library Online Contents | 2016