Current Location:home > Detailed Browse

Article Detail

Resonance Algorithm: A New Look at the Shortest Path Problem

Abstracts

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. Here we developed a novel nature-inspired algorithm to compute all possible shortest paths between two nodes in a graph: Resonance Algorithm (RA), which is surprisingly simple and intuitive. Besides its simplicity, RA turns out to be much more time-efficient for large-scale graphs than the extended Dijkstra's algorithm (such that it gives all possible shortest paths). Moreover, RA 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. These good properties ensure RA a wide range of applications.
Download Comment Hits:1226 Downloads:146
From: 刘宇
DOI:10.12074/202110.00056
Recommended references: Liu, Yu,Lin, Qiguang,Hong, Binbin,Hjerpe, Daniel,Liu, Xiaofeng.(2021).Resonance Algorithm: A New Look at the Shortest Path Problem.[ChinaXiv:202110.00056] (Click&Copy)
Version History
[V1] 2021-10-11 19:03:48 chinaXiv:202110.00056V1 Download
Related Paper

Download

Current Browse

Change Subject Browse