A Fast Bayesian Iterative Rule in Amoeba Algorithm
Qixuan Cai and Yong Deng
Shortest path (SP) problem is a classical problem in computer science. Many Physarum-inspired algorithms suffer from a low converge speed. To solve this problem, a bayesian iteration rule is proposed. Bayes formula is used to establish a relationship between flux and conductivity of each edge in iteration. And a compare function is proposed to handle negative weighted edges in the network. Computational experiments with different algorithms on approximating shortest paths in networks with different topologies are made, and number of nodes varying from 10 to 2000. The results show that the proposed method outperforms the original Physarum polycephalum Algorithm both on executing time and iterations. And the efficiency of the proposed method is close to Dijsktra algorithm. It can also solve SP problem in network with negative weighted edges.
Keywords: Shortest path, Physarum polycephalum, Bayes formula, negative weighted edge, slime mold, network optimization