The True Shortest Path of Obstacle Grid Graph Is Solved by SGP Vertex Extraction and Filtering Algorithm
Open Access
- 29 June 2025
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 18 (7) , 400
Abstract
In the obstacle grid map, due to the limitations in search direction imposed by classical path algorithms and meta-heuristic algorithms, the shortest paths are not the true shortest paths (TSPs) but rather the shortest grid paths (SGPs). This paper introduces an SGP vertex extraction and filtering algorithm (SGPVEFA) that identifies key nodes within SGPs. After screening, these nodes yield TSPs under the same conditions. Through various experiments, the shortest path length searched by the SGPVEFA proposed in this paper can be used to search for the real shortest path, and it also has advantages in comparison with recent new algorithms. With the increase in map scale and obstacle rate, the advantages of this path algorithm are more significant.Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (62402200)
This publication has 24 references indexed in Scilit:
- An efficient grid-based path planning approach using improved artificial bee colony algorithmKnowledge-Based Systems, 2025
- A comprehensive survey on the generalized traveling salesman problemEuropean Journal of Operational Research, 2023
- Path planning optimization in unmanned aerial vehicles using meta-heuristic algorithms: a systematic reviewEnvironmental Monitoring and Assessment, 2022
- Path-length analysis for grid-based path planningArtificial Intelligence, 2021
- An improved distance‐based ant colony optimization routing for vehicular ad hoc networksInternational Journal of Communication Systems, 2020
- Metaheuristic research: a comprehensive surveyArtificial Intelligence Review, 2018
- The vehicle routing problem: State of the art classification and reviewComputers & Industrial Engineering, 2016
- Clear and smooth path planningApplied Soft Computing, 2015
- Grey Wolf OptimizerAdvances in Engineering Software, 2014
- Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous SpacesJournal of Global Optimization, 1997