Heuristic static single-source-single-sink shortest path algorithm: cycle-reducing algorithm, 𝑨∗ algorithm and dynamic simulation method

Tianyu Liu; Cuicui Luo

doi:10.1117/12.3036576

21 July 2024 Heuristic static single-source-single-sink shortest path algorithm: cycle-reducing algorithm, 𝑨∗ algorithm and dynamic simulation method

Tianyu Liu, Cuicui Luo

Author Affiliations +

Proceedings Volume 13219, Fourth International Conference on Applied Mathematics, Modelling, and Intelligent Computing (CAMMIC 2024); 1321932 (2024) https://doi.org/10.1117/12.3036576
Event: 4th International Conference on Applied Mathematics, Modelling and Intelligent Computing (CAMMIC 2024), 2024, Kaifeng, China

Abstract

The shortest path problem has always been the most fundamental but extremely important problem in operations research and optimization research. Given a weighted graph (directed or undirected) 𝐺 = (𝑉, 𝐸, 𝜔) , |𝑉| = 𝑛, |𝐸| = 𝑚, and the two points s and t in G are the starting and ending points, respectively. The single source and single endpoint shortest path problem aims to find the shortest s-t path. The main contributions of this article are as follows: (1) Based on the cycle-reducing algorithm, algorithm, a hierarchical single-source single-sink shortest path algorithm is obtained. The advantage of this algorithm is that it runs faster and avoids accessing all vertices in the graph to save time and storage space. (2) Based on the 𝐴∗ algorithm, a new lower bound distance estimation function is proposed to solve the single source and single endpoint problem. (3) Propose a dynamic simulation-based method for solving the shortest path problem: embed a nonnegative weighted graph into Euclidean space and use dynamic simulation software to solve the shortest s-t path. The advantage of this method is that it is very accurate and can solve all the shortest s-t paths without visiting too many keyless points.

(2024) Published by SPIE. Downloading of the abstract is permitted for personal use only.

Citation Download Citation

Tianyu Liu and Cuicui Luo "Heuristic static single-source-single-sink shortest path algorithm: cycle-reducing algorithm, 𝑨∗ algorithm and dynamic simulation method", Proc. SPIE 13219, Fourth International Conference on Applied Mathematics, Modelling, and Intelligent Computing (CAMMIC 2024), 1321932 (21 July 2024); https://doi.org/10.1117/12.3036576

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available