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.