Dynamic physarum solver: A bio-inspired shortest path method of dynamically changing graphs
Turkish Journal of Electrical Engineering and Computer Sciences, cilt.27, sa.2, ss.1489-1503, 2019 (SCI-Expanded, Scopus, TRDizin)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 27 Sayı: 2
- Basım Tarihi: 2019
- Doi Numarası: 10.3906/elk-1811-46
- Dergi Adı: Turkish Journal of Electrical Engineering and Computer Sciences
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, TR DİZİN (ULAKBİM)
- Sayfa Sayıları: ss.1489-1503
- Anahtar Kelimeler: Dijkstra’s algorithm, Dynamic shortest path, M-matrix, Physarum Solver, Solution of linear systems
- Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
- Ankara Yıldırım Beyazıt Üniversitesi Adresli: Hayır
Özet
© TÜBİTAK.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 ∆-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.