{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:24:58Z","timestamp":1760711098901,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T00:00:00Z","timestamp":1672012800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T00:00:00Z","timestamp":1672012800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002726","name":"Beijing Normal University","doi-asserted-by":"crossref","award":["28705-310432106"],"award-info":[{"award-number":["28705-310432106"]}],"id":[{"id":"10.13039\/501100002726","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Key Research & Development Program","award":["2018AAA0100803"],"award-info":[{"award-number":["2018AAA0100803"]}]},{"name":"Key Research and Development Program of Jiangsu","award":["BK20192004","BE2018004-04"],"award-info":[{"award-number":["BK20192004","BE2018004-04"]}]},{"name":"Guangdong Forestry Science and Technology Innovation Project","award":["2020-KJCX005"],"award-info":[{"award-number":["2020-KJCX005"]}]},{"name":"Projects of International Cooperation and Exchanges of Changzhou","award":["CZ20200035"],"award-info":[{"award-number":["CZ20200035"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61803381","12205012"],"award-info":[{"award-number":["61803381","12205012"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Complex Intell. Syst."],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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: <jats:italic>Resonance Algorithm<\/jats:italic> (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\u2019s algorithm, which suggests that in those scenarios, RA could also be practically useful.<\/jats:p>","DOI":"10.1007\/s40747-022-00942-z","type":"journal-article","created":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T14:06:42Z","timestamp":1672063602000},"page":"4159-4167","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Resonance algorithm: an intuitive algorithm to find all shortest paths between two nodes"],"prefix":"10.1007","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2640-6490","authenticated-orcid":false,"given":"Yu","family":"Liu","sequence":"first","affiliation":[]},{"given":"Qiguang","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Binbin","family":"Hong","sequence":"additional","affiliation":[]},{"given":"Yunru","family":"Peng","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Hjerpe","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1310-6739","authenticated-orcid":false,"given":"Xiaofeng","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,26]]},"reference":[{"key":"942_CR1","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1002\/net.3230140208","volume":"14","author":"N Deo","year":"1984","unstructured":"Deo N, Pang C-Y (1984) Shortest-path algorithms: taxonomy and annotation. Networks 14:275\u2013323","journal-title":"Networks"},{"issue":"4","key":"942_CR2","doi-asserted-by":"publisher","first-page":"1304","DOI":"10.1109\/TCYB.2017.2691666","volume":"48","author":"X Zhang","year":"2018","unstructured":"Zhang X, Mahadevan S (2018) A bio-inspired approach to traffic network equilibrium assignment problem. IEEE Trans Cybern 48(4):1304\u20131315","journal-title":"IEEE Trans Cybern"},{"key":"942_CR3","doi-asserted-by":"crossref","unstructured":"Bast H, Delling D, Goldberg A, M\u00fcller-Hannemann M, Pajor T, Sanders P, Wagner D, Werneck RF (2016) Algorithm Engineering. Route Planning in Transportation Networks, pp 19\u201380. Springer, Cham","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"942_CR4","doi-asserted-by":"crossref","unstructured":"Delling D, Sanders P, Schultes D, Wagner D (2009) Algorithmics of Large and Complex Networks. Engineering Route Planning Algorithms, pp 117\u2013139. Springer, Berlin","DOI":"10.1007\/978-3-642-02094-0_7"},{"key":"942_CR5","doi-asserted-by":"crossref","unstructured":"Medhi D, Ramasamy K (2018) Chapter 2 - Routing Algorithms: Shortest Path, Widest Path, and Spanning Tree, Second edition edn. The Morgan Kaufmann Series in Networking, pp. 30\u201363. Morgan Kaufmann, Boston","DOI":"10.1016\/B978-0-12-800737-2.00003-X"},{"issue":"2","key":"942_CR6","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1109\/TCYB.2016.2519939","volume":"47","author":"H Mahboubi","year":"2017","unstructured":"Mahboubi H, Masoudimansour W, Aghdam AG, Sayrafian-Pour K (2017) An energy-efficient target-tracking strategy for mobile sensor networks. IEEE Trans Cybern 47(2):511\u2013523","journal-title":"IEEE Trans Cybern"},{"key":"942_CR7","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.future.2008.07.002","volume":"25","author":"F Dijkstra","year":"2009","unstructured":"Dijkstra F, van der Ham J, Grosso P, de Laat C (2009) A path finding implementation for multi-layer networks. Fut Gen Comput Syst 25:142\u2013146","journal-title":"Fut Gen Comput Syst"},{"key":"942_CR8","doi-asserted-by":"publisher","first-page":"1490","DOI":"10.1049\/el.2015.1244","volume":"51","author":"X Sun","year":"2015","unstructured":"Sun X, Liu Y, Yao W, Qi N (2015) Triple-stage path prediction algorithm for real-time mission planning of multi-UAV. Electron Lett 51:1490\u20131492","journal-title":"Electron Lett"},{"key":"942_CR9","doi-asserted-by":"publisher","first-page":"45618","DOI":"10.1109\/ACCESS.2020.2978122","volume":"8","author":"P Xiao","year":"2020","unstructured":"Xiao P, Ju H, Li Q, Xu H, Lu C (2020) Task planning of space maintenance robot using modified clustering method. IEEE Access 8:45618\u201345626","journal-title":"IEEE Access"},{"key":"942_CR10","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1:269\u2013271","journal-title":"Numer Math"},{"key":"942_CR11","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/j.procs.2012.04.060","volume":"9","author":"W Peng","year":"2012","unstructured":"Peng W, Hu X, Zhao F, Su J (2012) A fast algorithm to find all-pairs shortest paths in complex networks. Procedia Comput Sci 9:557\u2013566","journal-title":"Procedia Comput Sci"},{"issue":"13","key":"942_CR12","first-page":"6401","volume":"217","author":"X Lu","year":"2011","unstructured":"Lu X, Camitz M (2011) Finding the shortest paths by node combination. Appl Math Comput 217(13):6401\u20136408","journal-title":"Appl Math Comput"},{"issue":"2","key":"942_CR13","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.jda.2009.03.001","volume":"8","author":"JB Orlin","year":"2010","unstructured":"Orlin JB, Madduri K, Subramani K, Williamson M (2010) A faster algorithm for the single source shortest path problem with few distinct positive lengths. J Discrete Algorithm 8(2):189\u2013198","journal-title":"J Discrete Algorithm"},{"key":"942_CR14","doi-asserted-by":"crossref","unstructured":"Bang-Jensen J, Gutin G (2009) Digraphs: Theory, Algorithms and Applications, pp. 55\u201358. Springer, London. Chap. The Bellman-Ford-Moore algorithm","DOI":"10.1007\/978-1-84800-998-1"},{"issue":"2","key":"942_CR15","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/s00453-007-9062-1","volume":"50","author":"TM Chan","year":"2008","unstructured":"Chan TM (2008) All-pairs shortest paths with real weights in o(n$$^3$$ \/ log n) time. Algorithmica 50(2):236\u2013243","journal-title":"Algorithmica"},{"key":"942_CR16","doi-asserted-by":"crossref","unstructured":"Liu X, Li J, Hu F, Yang C (2019) Obstacle induced stochastic tree for fast path planning. In: 2019 IEEE International Conference on Real-time Computing and Robotics (RCAR), pp 499\u2013503","DOI":"10.1109\/RCAR47638.2019.9044003"},{"key":"942_CR17","doi-asserted-by":"crossref","unstructured":"Noto M, Sato H (2000) A method for the shortest path search by extended Dijkstra algorithm. In: 2000 IEEE international conference on systems, man and cybernetics, pp 2316\u20132320","DOI":"10.1109\/ICSMC.2000.886462"},{"key":"942_CR18","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/BF03398701","volume":"40","author":"VN Sastry","year":"2003","unstructured":"Sastry VN, Janakiraman TN, Mohideen SI (2003) New algorithms for multi objective shortest path problem. Opsearch 40:278\u2013298","journal-title":"Opsearch"},{"key":"942_CR19","doi-asserted-by":"crossref","unstructured":"Storandt S (2012) Quick and energy-efficient routes: Computing constrained shortest paths for electric vehicles. In: Proceedings of the 5th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pp. 20\u201325. Association for Computing Machinery, New York, NY, USA","DOI":"10.1145\/2442942.2442947"},{"key":"942_CR20","first-page":"726","volume":"15","author":"S Zhang","year":"2013","unstructured":"Zhang S, Liu X (2013) A new algorithm for finding the k shortest transport paths in dynamic stochastic networks. J Vibroeng 15:726\u2013735","journal-title":"J Vibroeng"},{"issue":"2","key":"942_CR21","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1109\/TSMCB.2012.2210212","volume":"43","author":"D Zhu","year":"2013","unstructured":"Zhu D, Huang H, Yang SX (2013) Dynamic task assignment and path planning of multi-AUV system based on an improved self-organizing map and velocity synthesis method in three-dimensional underwater workspace. IEEE Trans Cybern 43(2):504\u2013514","journal-title":"IEEE Trans Cybern"},{"issue":"1","key":"942_CR22","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10846-012-9740-3","volume":"70","author":"S Moon","year":"2013","unstructured":"Moon S, Oh E, Shim DH (2013) An integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamic environments. J Intell Robot Syst 70(1):303\u2013313","journal-title":"J Intell Robot Syst"},{"key":"942_CR23","first-page":"88","volume":"241","author":"MMB Pascoal","year":"2014","unstructured":"Pascoal MMB, Resende M (2014) The minmax regret robust shortest path problem in a finite multi-scenario model. Appl Math Comput 241:88\u2013111","journal-title":"Appl Math Comput"},{"issue":"1","key":"942_CR24","first-page":"198","volume":"198","author":"Y Ohtsubo","year":"2008","unstructured":"Ohtsubo Y (2008) Stochastic shortest path problems with associative accumulative criteria. Appl Math Comput 198(1):198\u2013208","journal-title":"Appl Math Comput"},{"key":"942_CR25","first-page":"780","volume":"267","author":"JL Gal\u00e1n-Garc\u00eda","year":"2015","unstructured":"Gal\u00e1n-Garc\u00eda JL, Aguilera-Venegas G, Gal\u00e1n-Garc\u00eda M\u00c1, Rodr\u00edguez-Cielos P (2015) A new probabilistic extension of Dijkstra\u2019s algorithm to simulate more realistic traffic flow in a smart city. Appl Math Comput 267:780\u2013789","journal-title":"Appl Math Comput"},{"issue":"1","key":"942_CR26","first-page":"247","volume":"185","author":"MH Xu","year":"2007","unstructured":"Xu MH, Liu YQ, Huang QL, Zhang YX, Luan GF (2007) An improved Dijkstra\u2019s shortest path algorithm for sparse network. Appl Math Comput 185(1):247\u2013254","journal-title":"Appl Math Comput"},{"key":"942_CR27","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/1290672.1290682","volume":"3","author":"J Hershberger","year":"2007","unstructured":"Hershberger J, Maxel M, Suri S (2007) Finding the k shortest simple paths: a new algorithm and its implementation. ACM Trans Algorithms 3:45","journal-title":"ACM Trans Algorithms"},{"key":"942_CR28","first-page":"913485","volume":"2012","author":"S Hemalatha","year":"2012","unstructured":"Hemalatha S, Valsalal P (2012) Identification of optimal path in power system network using bellman ford algorithm. Model Simul Eng 2012:913485","journal-title":"Model Simul Eng"},{"key":"942_CR29","doi-asserted-by":"publisher","first-page":"3123","DOI":"10.1073\/pnas.80.10.3123","volume":"80","author":"MS Waterman","year":"1983","unstructured":"Waterman MS (1983) Sequence alignments in the neighborhood of the optimum with general application to dynamic programming. Proc Natl Acad Sci 80:3123\u20133124","journal-title":"Proc Natl Acad Sci"},{"key":"942_CR30","doi-asserted-by":"publisher","first-page":"2720","DOI":"10.1039\/c3mb70089e","volume":"9","author":"M Jiang","year":"2013","unstructured":"Jiang M, Chen Y, Zhang Y, Chen L, Zhang N, Huang T, Cai Y-D, Kong X (2013) Identification of hepatocellular carcinoma related genes with k-th shortest paths in a protein-protein interaction network. Mol BioSyst 9:2720\u20132728","journal-title":"Mol BioSyst"},{"key":"942_CR31","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1137\/S0097539795290477","volume":"28","author":"D Eppstein","year":"1998","unstructured":"Eppstein D (1998) Finding the k shortest paths. SIAM J Comput 28:652\u2013673","journal-title":"SIAM J Comput"},{"key":"942_CR32","first-page":"217","volume":"41","author":"S Wang","year":"2014","unstructured":"Wang S, Li A (2014) Multi-adjacent-vertexes and multi-shortest-paths problem of Dijkstra algorithm. Comput Sci 41:217\u2013224","journal-title":"Comput Sci"},{"key":"942_CR33","first-page":"22","volume":"40","author":"K Mohanta","year":"2012","unstructured":"Mohanta K (2012) Comprehensive study on computational methods for k-shortest paths problem. Int J Comput Appl 40:22\u201326","journal-title":"Int J Comput Appl"},{"key":"942_CR34","doi-asserted-by":"crossref","unstructured":"Ziggelaar A (1980) The sine law of refraction derived from the principle of Fermat\u2014prior to Fermat? The theses of Wilhelm Boelmans S. J. in 1634. Centaurus 24, 246\u2013262","DOI":"10.1111\/j.1600-0498.1980.tb00377.x"},{"key":"942_CR35","doi-asserted-by":"publisher","first-page":"1267","DOI":"10.1103\/RevModPhys.76.1267","volume":"76","author":"M Schlosshauer","year":"2005","unstructured":"Schlosshauer M (2005) Decoherence, the measurement problem, and interpretations of quantum mechanics. Rev Mod Phys 76:1267\u20131305","journal-title":"Rev Mod Phys"},{"key":"942_CR36","doi-asserted-by":"crossref","unstructured":"Yang X-S, He X-S (2019) Nature-inspired algorithms, pp 21\u201340. Springer, Cham","DOI":"10.1007\/978-3-030-16936-7_2"},{"key":"942_CR37","doi-asserted-by":"crossref","unstructured":"Dorigo M, Birattari M, Stutzle T (2006) Ant colony optimization. IEEE Comput Intell Magn 1(4):28\u201339","DOI":"10.1109\/CI-M.2006.248054"},{"key":"942_CR38","doi-asserted-by":"crossref","unstructured":"Dorigo M, Blum C (2005) Ant colony optimization theory: a survey. Theor Comput Sci 344(2):243\u2013278","DOI":"10.1016\/j.tcs.2005.05.020"},{"key":"942_CR39","doi-asserted-by":"crossref","unstructured":"Guilmeau T, Chouzenoux E, Elvira V (2021) Simulated annealing: a review and a new scheme. In: 2021 IEEE Statistical Signal Processing Workshop (SSP), pp 101\u2013105","DOI":"10.1109\/SSP49050.2021.9513782"},{"issue":"2","key":"942_CR40","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.knosys.2011.07.001","volume":"26","author":"WT Pan","year":"2012","unstructured":"Pan WT (2012) A new fruit fly optimization algorithm: taking the financial distress model as an example. Knowl-Based Syst 26(2):69\u201374","journal-title":"Knowl-Based Syst"},{"key":"942_CR41","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.advengsoft.2016.01.008","volume":"95","author":"S Mirjalili","year":"2016","unstructured":"Mirjalili S, Lewis A (2016) The whale optimization algorithm. Adv Eng Softw 95:51\u201367","journal-title":"Adv Eng Softw"},{"issue":"6","key":"942_CR42","doi-asserted-by":"publisher","first-page":"2237","DOI":"10.1007\/s10462-019-09732-5","volume":"53","author":"HA Alsattar","year":"2020","unstructured":"Alsattar HA, Zaidan AA, Zaidan BB (2020) Novel meta-heuristic bald eagle search optimisation algorithm. Artif Intell Rev 53(6):2237\u20132264","journal-title":"Artif Intell Rev"},{"key":"942_CR43","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01299142","volume":"2","author":"RV Helgason","year":"1993","unstructured":"Helgason RV, Kennington JL, Stewart BD (1993) The one-to-one shortest-path problem: an empirical analysis with the two-tree Dijkstra algorithm. Comput Optim Appl 2:47\u201375","journal-title":"Comput Optim Appl"}],"container-title":["Complex &amp; Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-022-00942-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40747-022-00942-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-022-00942-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T13:21:00Z","timestamp":1690464060000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40747-022-00942-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,26]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["942"],"URL":"https:\/\/doi.org\/10.1007\/s40747-022-00942-z","relation":{},"ISSN":["2199-4536","2198-6053"],"issn-type":[{"type":"print","value":"2199-4536"},{"type":"electronic","value":"2198-6053"}],"subject":[],"published":{"date-parts":[[2022,12,26]]},"assertion":[{"value":"13 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}