MMM
YYYY
Resonance Algorithm: A New Look at the Shortest Path Problem
共振算法:最短路径问题的新视角
共鳴アルゴリズム:最短経路問題の新しい見方
공명 알고리즘: 최단 경로 문제에 대한 새로운 시각
Algoritmo de resonancia: una nueva mirada al problema de la ruta más corta
Algorithme de résonance : un nouveau regard sur le problème du plus court chemin
Алгоритм резонанса: новый взгляд на проблему кратчайшего пути
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, 11 October 2021
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.

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.
ChinaXiv_1
ChinaXiv_2
ChinaXiv_3
Reviews and Discussions
https://www.hotpaper.io/index.html
Self-polarized RGB device realized by semipolar micro-LEDs and perovskite-in-polymer films for backlight applications
A highly sensitive LITES sensor based on a multi-pass cell with dense spot pattern and a novel quartz tuning fork with low frequency
Multi-wavelength nanowire micro-LEDs for future high speed optical communication
Luminescence regulation of Sb3+ in 0D hybrid metal halides by hydrogen bond network for optical anti-counterfeiting
Breaking the optical efficiency limit of virtual reality with a nonreciprocal polarization rotator
Simultaneously realizing thermal and electromagnetic cloaking by multi-physical null medium
Generation of lossy mode resonances (LMR) using perovskite nanofilms
Acousto-optic scanning multi-photon lithography with high printing rate
Tailoring electron vortex beams with customizable intensity patterns by electron diffraction holography
Miniature tunable Airy beam optical meta-device
Data-driven polarimetric imaging: a review
Robust measurement of orbital angular momentum of a partially coherent vortex beam under amplitude and phase perturbations



Previous Article                                Next Article
About
|
Contact
|
Copyright © Hot Paper