(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
  • Tracing the formation of oxygen vacancies at the conductive LaAlO₃/SrTiO₃ interface via photoemission
  • Junyan Chen, Tobias Eul, Lu Lyu, Yaolong Li, Xiaoyong Hu, Xingkun Ning, Shufang Wang, Martin Aeschlimann, Qihuang Gong
  • Opto-Electronic Science
  • 2022-07-15
  • Photonic spin Hall effect: fundamentals and emergent applications
  • Shuoqing Liu, Shizhen Chen, Shuangchun Wen, Hailu Luo
  • Opto-Electronic Science
  • 2022-07-14
  • Research on Visual Detection Algorithm for Groove Feature Sizes by Means of Structured Light Projection
  • ZHA Anfei, LU Yonghua, WANG Mingxin, ZHU Huayu
  • Transactions of Nanjing University of Aeronautics & Astronautics
  • 2022-07-12
  • Active odd-mode-metachannel for single-conductor systems
  • Pei Hang He, Ling Yun Niu, Yi Fan, Hao Chi Zhang, Le Peng Zhang, Dayue Yao, Wen Xuan Tang, Tie Jun Cui
  • Opto-Electronic Advances
  • 2022-06-30
  • An overview on the principle of inkjet printing technique and its application in micro-display for augmented/virtual realities
  • Xiao Yang, Yue Lin, Tingzhu Wu, Zijun Yan, Zhong Chen, Hao-Chung Kuo, Rong Zhang
  • Opto-Electronic Advances
  • 2022-06-25
  • Photonic synapses with ultralow energy consumption for artificial visual perception and brain storage
  • Caihong Li, Wen Du, Yixuan Huang, Jihua Zou, Lingzhi Luo, Song Sun, Alexander O. Govorov, Jiang Wu, Hongxing Xu, Zhiming Wang
  • Opto-Electronic Advances
  • 2022-06-24
  • Range-Angle Dependent Beampattern Synthesis Method for OFDM-Based Passive Radar
  • RAO Yunhua, HE Hao, WAN Xianrong, YI Jianxin
  • Wuhan University Journal of Natural Sciences
  • 2022-06-24
  • Time resolved studies reveal the origin of the unparalleled high efficiency of one nanosecond laser ablation in liquids
  • Sarah Dittrich, Maximilian Spellauge, Stephan Barcikowski, Heinz P. Huber, Bilal Gökce
  • Opto-Electronic Advances
  • 2022-06-22
  • Nonlinear optics with structured light
  • Wagner Tavares Buono, Andrew Forbes
  • Opto-Electronic Advances
  • 2022-06-22
  • Relationship between adjustment of low water level and utilization of water depth in Shashi Reach in middle Yangtze River
  • Juan-juan Fang, Yun-ping Yang, Meng-lin Jia, Yu-de Zhu, Jian-jun Wang
  • Water Science and Engineering
  • 2022-06-21
  • Femtosecond laser-induced periodic structures: mechanisms, techniques, and applications
  • Yuchan Zhang, Qilin Jiang, Mingquan Long, Ruozhong Han, Kaiqiang Cao, Shian Zhang, Donghai Feng, Tianqing Jia, Zhenrong Sun, Jianrong Qiu, Hongxing Xu
  • Opto-Electronic Science
  • 2022-06-21

  • 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