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

Authors

HİLAL ARSLAN

DOI

10.3906/elk-1811-46

Abstract

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.

Keywords

Physarum Solver, dynamic shortest path, Dijkstra's algorithm, solution of linear systems, M-matrix

First Page

1489

Last Page

1503

Recommended Citation

ARSLAN, HİLAL (2019) "Dynamic Physarum Solver: a bio-inspired shortest path method of dynamically changing graphs," Turkish Journal of Electrical Engineering and Computer Sciences: Vol. 27: No. 2, Article 57. https://doi.org/10.3906/elk-1811-46
Available at: https://journals.tubitak.gov.tr/elektrik/vol27/iss2/57