The use of various algorithms for finding paths in graphs to solve problems of spatial development of transport infrastructure
https://doi.org/10.46973/0201-727X_2025_2_53
Abstract
The question of the applicability of the Dijkstra algorithm, A* and Breadth-first search for solving pathfinding problems in environments with obstacles is considered. These algorithms can be used to solve problems of spatial development of linear objects of land transport infrastructure.
A series of simple experiments were conducted with the algorithms in order to quantify their asymptotic complexity, i.e. the number of operations performed and the execution time of the algorithm in conditions of pathfinding in environments with obstacles. The series of experiments has a different configuration, determined by the direction of the search (unidirectional and bidirectional) and the method of cell passage (direct and mixed) and a variant of the search algorithm. When considering the A* algorithm, various metrics such as Chebyshev, Manhattan, and Euclidean distances were used as an additional parameter configuring the al gorithm's operation.
About the Author
D. V. Kuzmin
The Russian University of Transport (RUT MIIT)
Russian Federation
Russian Federation
Kuzmin Dmitry Vladimirovich, Chair “Logistics and Management of Transport Systems”, Candidate of Engineering Sciences, Associate Professor
References
1. Erdinç, A. İ. Automatic Pipeline Route Design with Multi-Criteria Evaluation Based on Least-Cost Path Analysis and Line-Based Cartographic Simplification: A Case Study of the Mus Project in Turkey / Ali İhsan Erdinç Örsan Ünal, Cevdet Coşkun Aydın // International Journal of Geo-Information (IJGI). – 2019. – Vol. 8 (4), No. 173. – DOI 10.3390/ijgi8040173
2. Kang, J. Y. Optimisation of pipeline route in the presence of obstacles based on a least cost path algorithm and Laplacian smoothing / J. Y. Kang, B. Lee // International Journal of Naval Architecture and Ocean Engineering. – 2017. – Vol. 9. – DOI 10.3390/ijgi8040173.
3. Scaparra, M. P. Corridor location: the multigateway shortest path / M. P. Scaparra, R. L. Church, F. A. Medrano // Journal of Geographical Systems. – 2014. – Vol. 16, No. 3. – P. 287–309. – DOI 10.1007/s10109-014-0197-8.
4. Yu, C. Extensions to least-cost path algorithms for roadway planning / C. Yu, J. Lee, M. Munro-Stasiuk // International Journal of Geographical Information Science. – 2003. – Vol. 17. – DOI 10.1080/1365881031000072645.
5. Path selection by topographic analysis: vector re-classification versus raster fuzzification as spatial multi-criteria using cost-path / A. A. Jamali, A. Esmailian, S. Mokhtarisabet, S. He // Spatial Information Research. – 2023. – Vol. 31. – DOI 10.1007/s41324-023-00539-9.
6. Stefano, B. Routing of power lines through least-cost path analysis and multicriteria evaluation to minimise environmental impacts / B. Stefano, G. Davide, O. Francesco // Environmental Impact Assessment Review. – 2011. – Vol. 31, No. 3. – P. 234–239. DOI 10.1016/j.eiar.2010.10.003. –
7. GIS Spatial Analysis Applied to Electric Line Routing Optimization / C. Monteiro, I. Ramírez-Rosado, V. Miranda [et al.] // IEEE Transactions on Power Delivery. – 2005. – Vol. 20. – P. 934–942. – DOI 10.1109/TPWRD.2004.839724.
8. Antikainen, H. Comparison of different strategies for determining raster‐based least‐cost paths with a minimum amount of distortion / H. Antikainen // Transactions in GIS. – 2013. – Vol. 17. – DOI 10.1111/j.14679671.2012.01355.x.
9. Tomlin, D. C. Propagating radial waves of travel cost in a grid / Dana C. Tomlin // International Journal of Geographical Information Science. – 2010. – Vol. 24, Iss. 9. – P. 1391–1413. – DOI 10.1080/13658811003779152.
10. Federal Law No. 33-FZ of 03/14/1995 (as amended on 08/08/2024) “On Specially Protected Natural Territories” (as amended and supplemented, effective from 03/01/2025). Article 2. Categories of specially protected natural territories, peculiarities of their creation and development // ConsultantPlus. – URL: https://www.consultant.ru/document/cons_doc_LAW_6072/ce98ed9bc2fc35acee2232585948a2b4bс927850 (date of access: 03/26/2025).
Review
For citations:
Kuzmin D.V. The use of various algorithms for finding paths in graphs to solve problems of spatial development of transport infrastructure. Vestnik Rostovskogo Gosudarstvennogo Universiteta Putej Soobshcheniya. 2025;(2):53-63. (In Russ.) https://doi.org/10.46973/0201-727X_2025_2_53
Views:
11
JATS XML
Email this article 