Некоторые алгоритмы поиска пути в графе:

• Поиск в ширину (BFS, Breadth-First Search). 1 Алгоритм в порядке очереди обходит каждую вершину графа. 5 Сначала исследуют одну вершину, из которой начинают путь, затем за один элементарный промежуток времени переходят к соседним не исследованным вершинам. 1
• Алгоритм Дейкстры (Dijkstra). 1 В процессе выполнения алгоритм проверяет каждую из вершин графа и находит кратчайший путь до исходной вершины. 1 Работает на взвешенном графе, у которого каждый путь имеет вес, то есть «стоимость». 1
• Алгоритм А* (А «со звёздочкой»). 1 Является расширением алгоритма Дейкстры, ускорение работы достигается за счёт эвристики. 1 При рассмотрении каждой отдельной вершины переход делается в ту соседнюю вершину, предположительный путь из которой до искомой вершины самый короткий. 1
• Поиск по первому наилучшему совпадению (Best-First Search). 1 Усовершенствованная версия алгоритма поиска в ширину, отличающаяся от оригинала тем, что в первую очередь развёртываются узлы, путь из которых до конечной вершины предположительно короче. 1
• IDA* (A* с итеративным углублением). 1 Изменённая версия A, использующая меньше памяти за счёт меньшего количества развёртываемых узлов. 1 Работает быстрее A в случае удачного выбора эвристики. 1
• Jump Point Search. 1 Ускоряет поиск пути, «перепрыгивая» многие места, которые должны быть просмотрены. 1 В отличие от подобных алгоритмов, JPS не требует предварительной обработки и дополнительных затрат памяти. 1