USING DIJKSTRA'S ALGORITHM TO SOLVE PROBLEMS OF SPATIAL DEVELOPMENT OF TRANSPORT INFRASTRUCTURE

The question of applicability of Dijkstra's algorithm for solving pathfinding problems in the context of spatial development of linear objects of land transport infrastructure is considered. This algorithm is widely used for various graph theory applications, including tracing and path planning. A number of simple experiments were carried out with the algorithm in order to determine quantitative indicators of its asymptotic complexity, i.e. the number of operations performed and the execution time of the al-gorithm. 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). Experiments with different implementations of the algorithm allow us to conclude that bidirec-tional search operations are 3.47 times less for direct and 2.69 times less for mixed (direct and diago-nal) cell traversals. However, the search execution time increases significantly. Moreover, there are a number of significant disadvantages of bidirectional search: the need to maintain two data structures for the search fronts of the starting and ending vertices, respectively; the mandatory presence of a tar-get vertex and uncertainty in the condition of stopping the search.