Dynamic Physarum Solver: a bio-inspired shortest path method of dynamically changing graphs

In dynamic graphs, edge weights of the graph change with time and solving the shortest path problem in such graphs is an important real-world problem. The studies in the literature require excessive computational time for computing the dynamic shortest path since determining changing edge weights is difficult especially when the graph size becomes large. In this paper, we propose a dynamic bio-inspired algorithm for finding the dynamic shortest path for large graphs based on Physarum Solver, which is a shortest path algorithm for static graphs. The proposed method is evaluated using three different large graph models representing diverse real-life applications. The effect of changing edge weights on the solution time is evaluated for each graph model separately and compared against $\Delta$-stepping, which is the most representative implementation of Dijkstra's algorithm. Experimental results show that the proposed method easily adapts edge weight changes and computes the dynamic shortest path efficiently.