The True Shortest Path of Obstacle Grid Graph Is Solved by SGP Vertex Extraction and Filtering Algorithm
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 a...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-06-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/7/400 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1999-4893 |