This paper presents an adaptive amoeba algorithm to address the shortest path tree (SPT) problem in dynamic graphs.In dynamic graphs, the edge weight updates consists of three categories: edge weight increases,edge weight decreases, the mixture of them.Existing works on this problem solve this issue through analyzing the nodes influenced by the edge weight updates and recompute these affected vertices.However, when the network becomes big, the process will become complex.The proposed method can overcome the disadvantages of the existing algorithms.The most important feature of this algorithm is its adaptivity.When the edge weight changes, the proposed algorithm can recognize the affected vertices and reconstruct them spontaneously.To evaluate the proposed adaptive amoeba algorithm, we compare it with the Label Setting algorithm and Dijkstra algorithm.The comparison results demonstrate the effectiveness of the proposed method.It also shows that it is appropriate to carry out different algorithms when the parameter ratio of changed weight (rcw) has different values.
Shortest path tree Bio-inspired algorithm Optimization Acyclic directed network
Xiaoge Zhang Felix T.S.Chan Sankaran Mahadevan Andrew Adamatzky Xiaowu Chen Yong Deng
School of Computer and Information Science, Southwest University, Chongqing, China Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hum,Kow School of Engineering, Vanderbilt University, Nashville, USA Unconventional Computing Center, University of the West of England, Bristol, UK State Key Laboratory of Virtual Reality Technology and Systems, School of Computer Science and Engin School of Computer and Information Science, Southwest University, Chongqing, China;School of Enginee