Resonance algorithm: an intuitive algorithm to find all shortest paths between two nodes

Autor: Yu Liu, Qiguang Lin, Binbin Hong, Yunru Peng, Daniel Hjerpe, Xiaofeng Liu
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Complex & Intelligent Systems, Vol 9, Iss 4, Pp 4159-4167 (2022)
Druh dokumentu: article
ISSN: 2199-4536
2198-6053
DOI: 10.1007/s40747-022-00942-z
Popis: Abstract The shortest path problem (SPP) is a classic problem and appears in a wide range of applications. Although a variety of algorithms already exist, new advances are still being made, mainly tuned for particular scenarios to have better performances. As a result, they become more and more technically complex and sophisticated. In this paper, we developed an intuitive and nature-inspired algorithm to compute all possible shortest paths between two nodes in a graph: Resonance Algorithm (RA). It can handle any undirected, directed, or mixed graphs, irrespective of loops, unweighted or positively weighted edges, and can be implemented in a fully decentralized manner. Although the original motivation for RA is not the speed per se, in certain scenarios (when sophisticated matrix operations can be employed, and when the map is very large and all possible shortest paths are demanded), it out-competes Dijkstra’s algorithm, which suggests that in those scenarios, RA could also be practically useful.
Databáze: Directory of Open Access Journals
Externí odkaz: