Using a breadth-first search algorithm in the process of spatial development of land transportation infrastructure

Aim. To examine the applicability of the breadth-first path searching algorithm for spatial development of linear land transportation infrastructure facilities. Methods. The paper uses Breadth-First Searching, a graph path searching algorithm that is widely used as part of various graph theory applications, including path tracing and path planning. A number of simple experiments were carried out with this algorithm in order to determine the quantitative indicators of its asymptotic complexity, i.e., the number of performed operations and the algorithm execution time. The series of experiments has a different structure that is defined by the search direction (unidirectional and bidirectional) and the method of cell scanning (direct and mixed). Conclusion. Experiments involving various implementations of the algorithm show that bidirectional search can significantly reduce the number of performed operations and the search time. Thus, the number of operations for bidirectional search is 2.75 times less for direct and 2.78 times less for mixed (direct and diagonal) cell scanning. Moreover, it is concluded that the bidirectional implementation of the algorithm has its own scope of efficient use. First, bidirectional search is effective in highly-branched graphs. The number of operations for bidirectional maze search decreases 57.07%, while the time of the same experiment decreases 76.92% as compared to the unidirectional search. In a corridor environment that, by definition, has weak branching, the difference in the number of performed operations between bidirectional and unidirectional search was 1.06%, while the execution time remained the same. Secondly, the efficiency of the algorithm is significantly reduced when the graph structure is complex. Thirdly, using this implementation requires confidence in the fact that a path between the starting and target nodes exists.

1. Automatic Pipeline Route Design with Multi-Criteria Evaluation Based on Least-Cost Path Analysis and LineBased Cartographic Simplification: A Case Study of the Mus Project in Turkey. (accessed 23.05.2025). Available at: https://www.mdpi.com/2220-9964/8/4/173.

2. Kang J.Y., Lee B. Optimisation of pipeline route in the presence of obstacles based on a least cost path algorithm and laplacian smoothing. International Journal of Naval Architecture and Ocean Engineering 2017;9.

3. Scaparra M.P., Church R.L., Medrano F.A. Corridor location: the multi-gateway shortest path model. Journal of Geographical Systems 2014;16(3):287-309.

4. Yu C., Lee J., Munro-Stasiuk M. Extensions to leastcost path algorithms for roadway planning. International Journal of Geographical Information Science – GIS 2003;17.

5. Jamali A.A., Esmailian A., Mokhtarisabet S. et al. Path selection by topographic analysis: vector re-classification versus raster fuzzification as spatial multi-criteria using cost-path. Spatial Information Research 2023;31.

6. Stefano B., Davide G., Francesco O. Routing of power lines through least-cost path analysis and multicriteria evaluation to minimise environmental impacts. Environmental Impact Assessment Review 2011;31(3):234-239.

7. Monteiro C., Ramírez-Rosado I., Miranda V. et al. GIS Spatial Analysis Applied to Electric Line Routing Optimization. Power Delivery, IEEE Transactions on 2005;20:934-942.

8. Antikainen H. Comparison of Different Strategies for Determining Raster-Based Least-Cost Paths with a Minimum Amount of Distortion. Transactions in GIS 2013;17.

9. C. Dana T. Propagating radial waves of travel cost in a grid. International Journal of Geographical Information Science 2010;24(9):1391-1413.

10. Ahuja R., Mehlhorn K., Orlin J. et al. Faster Algorithms for the Shortest Path Problem. J. ACM 1990;37:213-223.

11. Wayahdi M., Ginting S., Syahputra D. Greedy, A-Star, and Dijkstra’s Algorithms in Finding Shortest Path. International Journal of Advances in Data and Information Systems 2021;2:45-52.

12. Moore E.F. The Shortest Path through a Maze. In: Proc. International Symposium on the Theory of Switching, Part II. Harvard University Press; 1959.

13. Dijkstra E.W. A note on two problems in connexion with graphs. Numerische Mathematik 1959;1(1):269-271.

14. Cormen T.H., Leiserson C.E., Rivest R.L. et al. Introduction to Algorithms. MIT Press and McGraw-Hill; 2001.

15. Sedgewick R., Wayne K. Algorithms. AddisonWesley Professional; 2011.