Теоретичний аналіз ефективності алгоритмів пошуку шляху в графових моделях

Abstract

The work is devoted to the comparative analysis of algorithmic approaches to solving the problem of finding the shortest route in weighted graphs. The evolution of methods from classical brute-force algorithms to modern heuristic strategies is investigated. The computational complexity and functional features of Dijkstra's algorithm and the A* (Astar) algorithm are analyzed. The influence of the choice of heuristic function on the algorithm convergence speed and the optimality of the found solution is considered. The areas of appropriate use of each method depending on the topology of the studied space and memory resource requirements are determined.