{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T05:28:36Z","timestamp":1778822916293,"version":"3.51.4"},"reference-count":28,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T00:00:00Z","timestamp":1751155200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62402200"],"award-info":[{"award-number":["62402200"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a18070400","type":"journal-article","created":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T12:10:31Z","timestamp":1751285431000},"page":"400","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The True Shortest Path of Obstacle Grid Graph Is Solved by SGP Vertex Extraction and Filtering Algorithm"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1594-1789","authenticated-orcid":false,"given":"Yijie","family":"Zhang","sequence":"first","affiliation":[{"name":"School of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi 214126, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jizhou","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi 214126, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,6,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/j.cie.2015.12.007","article-title":"The vehicle routing problem: State of the art classification and review","volume":"99","author":"Braekers","year":"2016","journal-title":"Comput. Ind. Eng."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"819","DOI":"10.1016\/j.ejor.2023.07.022","article-title":"A comprehensive survey on the generalized traveling salesman problem","volume":"314","author":"Pop","year":"2024","journal-title":"Eur. J. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1016\/j.asoc.2015.04.017","article-title":"Clear and smooth path planning","volume":"32","author":"Davoodi","year":"2015","journal-title":"Appl. Soft Comput."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Dijkstra, E.W. (2022). A note on two problems in connexion with graphs. Edsger Wybe Dijkstra: His Life, Work, and Legacy, Association for Computing Machinery.","DOI":"10.1145\/3544585.3544600"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1038\/scientificamerican0792-66","article-title":"Genetic algorithms","volume":"267","author":"Holland","year":"1992","journal-title":"Sci. Am."},{"key":"ref_6","first-page":"509","article-title":"An Investigation of some Properties of an \u201cAnt Algorithm\u201d","volume":"92","author":"Alberto","year":"1992","journal-title":"PPSN"},{"key":"ref_7","unstructured":"Kennedy, J., and Eberhart, R. (December, January 27). Particle swarm optimization. Proceedings of the ICNN\u201995\u2014International Conference on Neural Networks, Perth, WA, Australia."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Katona, K., Neamah, H.A., and Korondi, P. (2024). Obstacle Avoidance and Path Planning Methods for Autonomous Navigation of Mobile Robot. Sensors, 24.","DOI":"10.3390\/s24113573"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2191","DOI":"10.1007\/s10462-017-9605-z","article-title":"Metaheuristic research: A comprehensive survey","volume":"52","author":"Hussain","year":"2019","journal-title":"Artif. Intell. Rev."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1023\/A:1018983524911","article-title":"Landscapes, operators and heuristic search","volume":"86","author":"Reeves","year":"1999","journal-title":"Ann. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/s10661-022-10590-y","article-title":"Path planning optimization in unmanned aerial vehicles using meta-heuristic algorithms: A systematic review","volume":"195","author":"Yahia","year":"2023","journal-title":"Environ. Monit. Assess."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2927","DOI":"10.1109\/TKDE.2016.2594065","article-title":"Efficient Algorithms for Temporal Path Computation","volume":"28","author":"Wu","year":"2016","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1109\/TKDE.2017.2773492","article-title":"Finding Top-k Shortest Paths with Diversity","volume":"30","author":"Liu","year":"2018","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"15570","DOI":"10.1109\/ACCESS.2021.3053295","article-title":"An Effective Genetic Algorithm for Solving the Clustered Shortest-Path Tree Problem","volume":"9","author":"Cosma","year":"2021","journal-title":"IEEE Access"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"e4502","DOI":"10.1002\/dac.4502","article-title":"An improved distance-based ant colony optimization routing for vehicular ad hoc networks","volume":"33","author":"Ramamoorthy","year":"2020","journal-title":"Int. J. Commun. Syst."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"103560","DOI":"10.1016\/j.artint.2021.103560","article-title":"Path-length analysis for grid-based path planning","volume":"301","author":"Bailey","year":"2021","journal-title":"Artif. Intell."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1613\/jair.5442","article-title":"The length of shortest vertex paths in binary occupancy grids compared to shortest r-constrained ones","volume":"59","author":"Hew","year":"2017","journal-title":"J. Artif. Intell. Res."},{"key":"ref_18","first-page":"85","article-title":"Any-angle path planning","volume":"34","author":"Alex","year":"2013","journal-title":"AI Mag."},{"key":"ref_19","unstructured":"Daniel, H., and Grastien, A. (2013, January 10\u201314). An optimal any-angle pathfinding algorithm. Proceedings of the International Conference on Automated Planning and Scheduling, Rome, Italy."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Yap, P., Burch, N., Holte, R.C., and Schaeffer, J. (2011, January 10\u201314). Any-angle path planning for computer games. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, Palo Alto, CA, USA.","DOI":"10.1609\/aiide.v7i1.12445"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Roy, M., Foufou, S., Koschan, A., Truchetet, F., and Abidi, M. (2004). Multiresolution analysis for irregular meshes. Wavelet Applications in Industrial Processing, SPIE.","DOI":"10.1117\/12.515974"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/j.advengsoft.2013.12.007","article-title":"Grey wolf optimizer","volume":"69","author":"Mirjalili","year":"2014","journal-title":"Adv. Eng. Softw."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1023\/A:1008202821328","article-title":"Differential Evolution\u2014A Simple and Efficient Heuristic for global Optimization over Continuous Spaces","volume":"11","author":"Storn","year":"1997","journal-title":"J. Glob. Optim."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1080\/21642583.2019.1708830","article-title":"A novel swarm intelligence optimization approach: Sparrow search algorithm","volume":"8","author":"Xue","year":"2020","journal-title":"Syst. Sci. Control. Eng."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"113528","DOI":"10.1016\/j.knosys.2025.113528","article-title":"An efficient grid-based path planning approach using improved artificial bee colony algorithm","volume":"318","author":"Yildirim","year":"2025","journal-title":"Knowl.-Based Syst."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Zhai, R., Xiao, P., Shu, D., Sun, Y., and Jiang, M. (2023). Application of improved butterfly optimization algorithm in mobile robot path planning. Electronics, 12.","DOI":"10.3390\/electronics12163424"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"4670","DOI":"10.1109\/TII.2019.2941916","article-title":"Obstacle avoidance and tracking control of redundant robotic manipulator: An RNN-based metaheuristic approach","volume":"16","author":"Khan","year":"2019","journal-title":"IEEE Trans. Ind. Inform."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1109\/JAS.2020.1003048","article-title":"BAS-ADAM: An ADAM based approach to improve the performance of beetle antennae search optimizer","volume":"7","author":"Khan","year":"2020","journal-title":"IEEE\/CAA J. Autom. Sin."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/7\/400\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:01:14Z","timestamp":1760032874000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/7\/400"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,29]]},"references-count":28,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2025,7]]}},"alternative-id":["a18070400"],"URL":"https:\/\/doi.org\/10.3390\/a18070400","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,29]]}}}