Rapid Physarum Algorithm for shortest path problem

• A heuristic method is proposed to make a bio-inspired algorithm, called as Physarum Algorithm, more efficient.
• We have demonstrated the efficiency of the proposed Rapid Physarum Algorithm on a variety of networks.
• The proposed Rapid Physarum Algorithm greatly decreases the time consumption of this bio-inspired mathematic model.

As shortest path (SP) problem has been one of the most fundamental network optimization problems for a long time, technologies for this problem are still being studied. In this paper, a new method by integrating a path finding mathematical model, inspired by Physarum polycephalum, with extracted one heuristic rule to solve SP problem has been proposed, which is called Rapid Physarum Algorithm (RPA). Simulation experiments have been carried out on three different network topologies with varying number of nodes. It is noted that the proposed RPA can find the optimal path as the path finding model does for most networks. What is more, experimental results show that the performance of RPA surpasses the path finding model on both iterations and solution time.

The randomly generated networks of various sizes are used to construct shortest path finding problem. The generated networks are undirected and fully connected, which guarantees that there exists at least one path from each node to every other node in the network. The length Lij of each edge is uniformly distributed random integer in the range [1,1000]. The comparison results illustrate the efficiency of the proposed Rapid Physarum Algorithm, which performs stably with the iterations increase in a narrow range as the number of nodes varies from 100 to 1000. As the number of nodes increases, the model exhibits excessive solution time, while the time RPA spends increases at a low growth. As a consequence, our proposed RPA is superior to the existing model. Figure optionsDownload as PowerPoint slide