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

Abstract

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.

Keywords

• Dijkstra’s algorithm
• Large-scale graph
• Nature-inspired algorithm
• Decentralized algorithm
• Fermat’s principle