A Parallel Fully Dynamic Iterative Bio-Inspired Shortest Path Algorithm

摘要

We propose a fully dynamic bio-inspired parallel algorithm for solving the shortest path problem on dynamically changing graphs based on Physarum Solver, which is an amoeba shortest path algorithm. Although many sequential algorithms exist for solving dynamic shortest path problem, there are only few parallel algorithms, most of which identify the set of vertices affected by the dynamic changes. However, when the graph size becomes large, the process of determining affected vertices is time-consuming. In fact, when the percentage of changing edges is large, most of the studies in the literature are infeasible. The proposed algorithm is able to identify affected vertices and reconstruct them spontaneously in parallel. Moreover, it is designed to be suitable for dynamically changing graphs since it uses the information arising in earlier iterations. Thus, it computes effectively dynamic shortest path even if percentage of changing edges is large. At each iteration of the proposed algorithm, a sparse linear system of equations needs to be solved, which is the most time-consuming and challenging step of the algorithm especially when the problem size is large. We propose a parallel preconditioned iterative method for solving those sparse linear systems. The proposed preconditioner is specifically designed based on the properties of the coefficient matrix of those linear systems, and the effectiveness of the proposed preconditioner is compared against other state-of-the-art preconditioners on dynamic graphs. The proposed algorithm is evaluated using three different large graph models representing diverse real-life applications on a parallel multicore cluster. The parallel scalability of the proposed algorithm is compared against Δ-stepping, which is the most representative parallel implementation of Dijkstra’s algorithm in the Parallel Boost Graph Library.