A hybrid single-source shortest path algorithm

The single-source shortest path problem arises in many applications, such as roads, social applications, andcomputer networks. Finding the shortest path is challenging, especially for graphs that contain a large number of verticesand edges. In this work, we propose a novel hybrid method that first sparsifies a given graph by removing most edges thatcannot form the shortest path tree and then applies a classical shortest path algorithm to the sparser graph. Removing allthe edges that cannot form the shortest path tree would be expensive since it is equivalent to solving the original problem.Therefore, we propose an iterative bioinspired algorithm, namely the Physarum algorithm, as the first stage to sparsifythe graph. We prove that the resulting sparser graph always contains the shortest path tree of the original graph. Next,a state-of-the-art algorithm such as Dijkstra’s is applied to find the single-source shortest path on the resulting graph.The proposed method is therefore a two-stage hybrid algorithm and it computes the single-source shortest path exactly.We compare the accuracy and solution time of the proposed hybrid method against state-of-the-art implementation ofDijkstra’s algorithm and the BFS algorithm on directed weighted and unweighted graphs, respectively, as a baseline.The results show that the proposed hybrid method achieves a significant speed improvement compared to the baseline.

PDF

___

[1] Ertl G. Shortest path calculation in large road networks. Operations Research Spektrum 1998; 20 (1): 15-20.
[2] Nguyen UT, Xu J. Multicast routing in wireless mesh networks: minimum cost trees or shortest path trees? IEEE Communications Magazine 2007; 45 (11): 72-77.
[3] Gong M, Li G, Wang Z, Ma L, Tian D. An efficient shortest path approach for social networks based on community structure. CAAI Transactions on Intelligence Technology 2016; 1 (1): 114-123.
[4] Bauer F, Varma A. Distributed algorithms for multicast path setup in data networks. In: Proceedings of GLOBECOM ’95; Singapore; 1995. pp. 1374-1378.
[5] Rescigno AA. Optimally balanced spanning tree of the star network. IEEE Transactions on Computers 2001; 50: 88- 91.
[6] Dijkstra EW. A note on two problems in connexion with graphs. Numerische Mathematics 1959; 1: 269-271.
[7] Bellman R. On a routing problem. Quarterly of Applied Mathematics 1958; 16: 87-90.
[8] Ahn CW, Ramakrishna RS. A genetic algorithm for shortest path routing problem and the sizing of populations. IEEE Transactions on Evolutionary Computation 2002; 6: 566-579.
[9] Dorigo M, Gambardella LM. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1997; 1 (1): 53-66.
[10] 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: 115-119.
[11] Nakagaki T, Yamada T, Toth A. Maze-solving by an amoeboid organism. Nature 2000; 407: 470.
[12] 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: 353-369.
[13] 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.
[14] 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.
[15] Zhang X, Zhang Y, Zhang Z, Mahadevan S. Rapid Physarum algorithm for shortest path problem. Applied Soft Computing 2014; 23: 19-26.
[16] Gao C, Zhang X, Yue Z, Wei D. An accelerated Physarum solver for network optimization. IEEE Transactions on Cybernetics (in press).
[17] Liu L, Song Y, Zhang H, Ma H. Physarum optimization: a biology-inspired algorithm for the Steiner tree problem in networks. IEEE Transactions on Computers 2015; 64: 818-831.
[18] Zhang X, Adamatzky A, Yang H, Mahadaven S, Yang XS et al. A bio-inspired algorithm for identification of critical components in the transportation networks. Applied Mathematics and Computation 2014; 248: 18-27.
[19] 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 In: IEEE INFOCOM; Orlando, FL, USA; 2012. pp. 1296- 1304.
[20] Li K, Torres CE, Thomas K, Rossi LF, Shen CC. Slime mold inspired routing protocols for wireless sensor networks. Swarm Intelligence 2011; 5: 183-223.
[21] 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.
[22] Zhang X, Huang S, Hu Y, Zhang Y, Mahadevan S et al. Solving 0-1 knapsack problems based on amoeboid organism algorithm. Applied Mathematics and Computation 2013; 219: 9959-9970.
[23] Zhang X, Chan FT, Yang H, Deng Y. An adaptive amoeba algorithm for shortest path tree computation in dynamic graphs. Information Sciences 2017; 405: 123-140.
[24] Xu S, Jiang W, Deng X, Shou Y. A modified Physarum-inspired model for the user equilibrium traffic assignment problem. Applied Mathematical Modelling 2018; 55: 340-353.
[25] Arslan H, Manguoglu M. A parallel bio-inspried shortest path algorithm; Computing 2019; 101: 969–988. doi: 10.1007/s00607-018-0621-x
[26] Adamatzky A. A would-be nervous system made from a slime mold. Artificial Life 2015; 21 (1): 73-91.
[27] Jones J. Characteristics of pattern formation and evolution in approximations of Physarum transport networks. Artificial Life 2010; 16 (2): 127-153.
[28] Meyer B. Optimal information transfer and stochastic resonance in collective decision making. Swarm Intelligence 2017; 11 (2): 131-154.
[29] Liang M, Gao C, Zhang Z. A new genetic algorithm based on modified Physarum network model for bandwidth-delay constrained least-cost multicast routing. Natural Computing 2017; 16 (1): 85-98.
[30] Zhang X, Zhang Y, Deng Y. An improved bio-inspired algorithm for the directed shortest path problem. Bioinspiration and Biomimetics 2014; 9 (4): 046016.
[31] Erdos P, Renyi A. On the evaluation of random graphs. Mathematical Institute of the Hungarian Academy of Sciences 1960; 5 (7): 17-61.
[32] Khorasani F, Gupta R, Bhuyan LN. Scalable SIMD-efficient graph processing on GPUs. In: Proceedings of the 24th International Conference on Parallel Architectures and Compilation Techniques; Limassol, Cyprus; 2018. p 39-50.
[33] Chakrabarti D, Zhan Y, Faloutsos C. R-MAT: A recursive model for graph mining. In: Proceedings of the 2004 SIAM International Conference on Data Mining; Florida, USA; 2004. p. 442-446.
[34] Becchetti L, Bonifaci V, Dirnberger M, Karrenbauer A, Mehlhorn K. Physarum can compute shortest paths: convergence proofs and complexity bounds. In: Automata Languages and Programming: 40th International Colloquium; Riga, Latvia; 2013. p. 472-483.