Dynamic Physarum Solver: a bio-inspired shortest path method of dynamically changing graphs

In dynamic graphs, edge weights of the graph change with time and solving the shortest path problem insuch graphs is an important real-world problem. The studies in the literature require excessive computational time for computing the dynamic shortest path since determining changing edge weights is difficult especially when the graph size becomes large. In this paper, we propose a dynamic bio-inspired algorithm for finding the dynamic shortest path for large graphs based on Physarum Solver, which is a shortest path algorithm for static graphs. The proposed method is evaluated using three different large graph models representing diverse real-life applications. The effect of changing edge weights on the solution time is evaluated for each graph model separately and compared against ∆-stepping, which is the most representative implementation of Dijkstra’s algorithm. Experimental results show that the proposed method easily adapts edge weight changes and computes the dynamic shortest path efficiently.

PDF

___

[1] King V. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: 40th Annual Symposium on Foundations of Computer Science; Washington, DC, USA; 1999. p. 81–89.
[2] Demetrescu C, Italiano GF. Fully dynamic all pairs shortest paths with real edge weights. In: Proceedings 2001 IEEE International Conference on Cluster Computing; Las Vegas, Nevada, USA; 2001. p. 260–267.
[3] Narvaez P, Siu KY, Tzeng HY. New dynamic algorithms for shortest path tree computation. IEEE/ACM Transactions on Networking 2000; 8 (6): 734–746.
[4] Zhang X, Chan FTS, Yang H, Deng Y. An adaptive amoeba algorithm for shortest path tree computation in dynamic graphs. Information Sciences 2017; 405: 123–140.
[5] Narvaez P, Siu KY, Tzeng HY. New dynamic SPT algorithm based on a ball-and-string model. IEEE/ACM Transactions on Networking 2001; 9 (6): 706–718.
[6] Chan EPF, Yang Y. Shortest Path Tree Computation in Dynamic Graphs. IEEE Transactions on Computers 2009; 58 (4): 541–557.
[7] Ramalingam G, Reps T. An Incremental Algorithm for a Generalization of the Shortest-Path Problem. Journal of Algorithms 1996; 21 (2): 267–305.
[8] Frigioni D, Marchetti-Spaccamela A, Nanni U. Fully Dynamic Algorithms for Maintaining Shortest Paths Trees. Journal of Algorithms 2000; 34 (2): 251–281.
[9] Frigioni D, Marchetti-Spaccamela A, Nanni U. Fully Dynamic Output Bounded Single Source Shortest Path Problem. In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms; Atlanta, Georgia, USA; 1996. p. 212–221.
[10] Frigioni D, Ioffreda M, Nanni U, Pasqualone G. Experimental Analysis of Dynamic Algorithms for the Single Source Shortest Paths Problem. ACM Journal on Experimental Algorithmics 1998; 3 (5).
[11] Tero A, Kobayashi R, Nakagaki T. Physarum solver: A biologically inspired method of road-network navigation. Physica A: Statistical Mechanics and its Applications 2006; 363 (1): 115–119.
[12] Tero A, Kobayashi R, Nakagaki T. A mathematical model for adaptive transport network in path finding by true slime mold. Journal of Theoretical Biology 2007; 244 (4): 553–564.
[13] Miyaji T, Ohnishi I. Physarum Can Solve the Shortest Path Problem on Riemann Surface Mathematically Rigorously. International Journal of Pure and Applied Mathematics 2008; 47 (3): 353–369.
[14] Liu L, Song Y, Zhang H, Ma H, Vasilakos AV. Physarum Optimization: A Biology-Inspired Algorithm for the Steiner Tree Problem in Networks. IEEE Transactions on Computers 2015; 64 (3): 818–831.
[15] Zhang X, Adamatzky A, Yang H, Mahadaven S, Yang XS, Wang Q, et al. A bio-inspired algorithm for identification of critical components in the transportation networks. Applied Mathematics and Computation 2014; 248: 18–27.
[16] Liu L, Song Y, Ma H, Zhang X. Physarum optimization: A biology-inspired algorithm for minimal exposure path problem in wireless sensor networks. In: 2012 Proceedings IEEE INFOCOM; Orlando, FL, USA; 2012. p. 1296–1304.
[17] Zhang Z, Gao C, Liu Y, Qian T. A universal optimization strategy for ant colony optimization algorithms based on the Physarum -inspired mathematical model. Bioinspiration and Biomimetics 2014; 9 (3):036006.
[18] Zhang X, Huang S, Hu Y, Zhang Y, Mahadevan S, Deng Y. Solving 0-1 knapsack problems based on amoeboid organism algorithm. Applied Mathematics and Computation 2013; 219 (19): 9959–9970.
[19] Arslan H, Manguoglu M. A parallel bio-inspired shortest path algorithm. Computing 2018; doi: 10.1007/s00607- 018-0621-x.
[20] Zhang X, Zhang Z, Zhang Y, Wei D, Deng Y. Route selection for emergency logistics management: A bio-inspired algorithm. Safety Science 2013; 54 :87–91. doi: 10.1016/j.ssci.2012.12.003.
[21] Zhang X, Adamatzky A, Chan FTS, Deng Y, Yang H, Yang XS, et al. A Biologically Inspired Network Design Model. Scientific Reports 2015; 5 (10794). doi: 10.1038/srep10794.
[22] Zhang X, Zhang Y, Deng Y. An improved bio-inspired algorithm for the directed shortest path problem. Bioinspiration & Biomimetics 2014; 9 (4):046016.
[23] Plemmons RJ. M-matrix characterizations.I-nonsingular M-matrices. Linear Algebra and its Applications 1977; 18 (2):175–188.
[24] Becchetti L, Bonifaci V, Dirnberger M, Karrenbauer A, Mehlhorn K. Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds. In: ICALP’13 Proceedings of the 40th international conference on Automata, Languages, and Programming - Volume Part II; Riga, Latvia; 2013. p. 472–483.
[25] Madduri K, Bader DA, Berry JW, Crobak JR. An Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-scale Graph Instances. In: Proceedings of the Meeting on Algorithm Engineering & Expermiments; Philadelphia, PA, USA; 2007. p. 23–35.
[26] Meyer U, Sanders P. ∆-stepping: a parallelizable shortest path algorithm. Journal of Algorithms 2003; 49:114–152.
[27] Meyer U, Sanders P. ∆-stepping: A Parallel Single Source Shortest Path Algorithm. In: European Symposium on Algorithms; Venice, Italy; 1998. p. 393–404.
[28] Shewchuk JR. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. Pittsburgh, PA, USA: Technical Report, School of Computer Science, Carnegie Mellon University; 1994.
[29] Wang Q, Lu X, Zhang X, Deng Y, Xiao C. An anticipation mechanism for the shortest path problem based on Physarum polycephalum. International Journal of General Systems 2015; 44 (3): 326–340.
[30] Liu X, Wang H. Dynamic Graph Shortest Path Algorithm. In: Web-Age Information Management; Harbin, China; 2012. p. 296–307.
[31] Demetrescu C, Goldberg AV, Johnson DS. Implementation Challenge for Shortest Paths. Boston, MA: Springer US; 2008.
[32] Erdos P, Renyi A. On the evaluation of random graphs. Mathematical Institute of the Hungarian Academy of Sciences 1960; 5:17–61.
[33] Watts DJ, Strogatz SH. Collective dynamics of small-world networks. Nature 1998; 393 (6684):440–442.
[34] Balay S, Gropp WD, McInnes LC, Smith BF. Efficient Management of Parallelism in Object Oriented Numerical Software Libraries. Cambridge, MA, USA: Birkhäuser Press; 1997.
[35] Edmonds N, Breuer A, Gregor D, Lumsdaine A. Single-Source Shortest Paths with the Parallel Boost Graph Library. In: The Ninth DIMACS Implementation Challenge - The Shortest Path Problem; Piscataway, NJ; 2006. p. 219–248.