This paper presents an adaptive amoeba algorithm to address the shortest pathtree (SPT) problem in dynamic graphs. In dynamic graphs, the edge weightupdates consists of three categories: edge weight increases, edge weightdecreases, the mixture of them. Existing work on this problem solve this issuethrough analyzing the nodes influenced by the edge weight updates and recomputethese affected vertices. However, when the network becomes big, the processwill become complex. The proposed method can overcome the disadvantages of theexisting approaches. The most important feature of this algorithm is itsadaptivity. When the edge weight changes, the proposed algorithm can recognizethe affected vertices and reconstruct them spontaneously. To evaluate theproposed adaptive amoeba algorithm, we compare it with the Label Settingalgorithm and Bellman-Ford algorithm. The comparison results demonstrate theeffectiveness of the proposed method.
展开▼
