(Preprint) Resonance Algorithm: A New Look at the Shortest Path Problem
Yu LIU 刘宇 ¹, Qiguang LIN 林麒光 ², Binbin HONG 洪斌斌 ³, Daniel HJERPE ⁴, Xiaofeng LIU 刘小峰 ² ⁵
¹ International Academic Center of Complex Systems, Beijing Normal University at Zhuhai, Zhuhai 519087, Guangdong, China
中国 广东 珠海 北京师范大学(珠海)复杂系统国际科学中心
² College of IoT Engineering, Hohai University, Changzhou 213022, Jiangsu, China
中国 江苏 常州 河海大学物联网工程学院
³ Institute of Microscale Optoelectronics, Shenzhen University, Shenzhen 518060, Guangdong, China
中国 广东 深圳 深圳大学微纳光电子学研究院
⁴ Ericsson AB, Kista 16483, Sweden
⁵ Jiangsu Key laboratory of Special Robotic Technologies, Changzhou 213022, Jiangsu, China
中国 江苏 常州 江苏省特种机器人技术重点实验室
ChinaXiv, 2021-10-11

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.
Resonance Algorithm: A New Look at the Shortest Path Problem_1
Resonance Algorithm: A New Look at the Shortest Path Problem_2
Resonance Algorithm: A New Look at the Shortest Path Problem_3
  • Cell-free chemoenzymatic starch synthesis from carbon dioxide
  • Tao Cai, Hongbing Sun, Jing Qiao, Leilei Zhu, Fan Zhang, Jie Zhang, Zijing Tang, Xinlei Wei, Jiangang Yang, Qianqian Yuan, Wangyin Wang, Xue Yang, Huanyu Chu, Qian Wang, Chun You, Hongwu Ma, Yuanxia Sun, Yin Li, Can Li, Huifeng Jiang, Qinhong Wang, Yanhe Ma
  • Science
  • 2021-09-24
  • Dating the First Case of COVID-19 Epidemic from a Probabilistic Perspective
  • Zhouwang Yang, Yunhe Hu, Zhiwei Ding, Tiande Guo
  • ChinaXiv
  • 2021-09-22
  • Scattered seeding of CAR T cells in solid tumors augments anticancer efficacy
  • Hongjun Li, Zejun Wang, Edikan Archibong, Qing Wu, Guojun Chen, Quanyin Hu, Tianyuan Ci, Zhaowei Chen, Jinqiang Wang, Di Wen, Hongwei Du, Jie Jiang, Jie Sun, Xingcai Zhang, Gianpietro Dotti, Zhen Gu
  • National Science Review
  • 2021-09-21
  • Intrinsically inert hyperbranched interlayer for enhanced stability of organic solar cells
  • Yawen Li, Tengfei Li, Jiayu Wang, Xiaowei Zhan, Yuze Lin
  • Science Bulletin
  • 2021-09-21
  • Self-energy dynamics and mode-specific phonon threshold effect in a Kekulé-ordered graphene
  • Hongyun Zhang, Changhua Bao, Michael Schüler, Shaohua Zhou, Qian Li, Laipeng Luo, Wei Yao, Zhong Wang, Thomas P Devereaux, Shuyun Zhou
  • National Science Review
  • 2021-09-16
  • Integrated 'all-in-one' strategy to stabilize zinc anodes for high-performance zinc-ion batteries
  • Canpeng Li, Xuesong Xie, Hui Liu, Pinji Wang, Canbin Deng, Bingan Lu, Jiang Zhou, Shuquan Liang
  • National Science Review
  • 2021-09-15
  • Literature review: non-intubated (tubeless) VATS for lung volume reduction surgery
  • Yi Zhang, Xin Jin
  • Video-Assisted Thoracic Surgery
  • 2021-09-15
  • Non-intubated thoracic surgery: an Asian perspective
  • Shuben Li, Yunpeng Zhong, Zhuxing Chen, Jun Liu, Jianxing He, Alan D. L. Sihoe
  • Video-Assisted Thoracic Surgery
  • 2021-09-15
  • A case of infectious endophthalmitis misdiagnosed as uveitis
  • Liu Xueying Zhong, Hongyi Shen, Wanwen Shao, Yongxin Zheng
  • Annals of Eye Science
  • 2021-09-15
  • A narrative review of glaucoma screening from fundus images
  • Xingxing Cao, Xu Sun, Shuai Yan, Yanwu Xu
  • Annals of Eye Science
  • 2021-09-15
  • Structured eigenvalue problems in electronic structure methods from a unified perspective
  • Zhendong Li
  • Chinese Journal of Chemical Physics
  • 2021-09-14
  • Contrast-enhanced ultrasound as a valuable imaging modality for characterizing testicular lesions
  • Jie Yu, Xin-Hui Jiang, Lian-Fang Du, Min Bai, Zhao-Jun Li, Qiu-Sheng Shi, Qi Jiang, Fan Li
  • Asian Journal of Andrology
  • 2021-09-14

  • Flexible Diodes/Transistors Based on Tunable p-n-Type Semiconductivity in Graphene/Mn-Co-Ni-O Nanocomposites                                Molecular imprinting and cladding produces antibody mimics with significantly improved affinity and specificity
    Copyright © PubCard