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

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