The use of various algorithms for finding paths in graphs to solve problems of spatial development of transport infrastructure

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 algorithm's operation.