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

• Алгоритм Дейкстры. 3 Строит маршрут пошагово, выбирая на каждом шаге наименее отдалённую вершину и двигаясь к ней, затем к следующей — и так, пока не доберётся до цели. 3
• Алгоритм A*. 23 На каждом шаге оценивает множество частичных путей и генерирует новые, расширяя наиболее многообещающий путь из множества. 2 Для этого A* хранит частичные пути в очереди с приоритетами, отсортированном по приблизительной длине — истинной измеренной длине пути плюс примерное оставшееся расстояние до цели. 2
• Метод «метлы». 1 Основан на построении однотипных таблиц. 1 Первым шагом выбирается начальная вершина, до неё расстояние равно «0», а до всех остальных вершин — бесконечно большому числу. 1 Вторым шагом определяется длина пути до соседних вершин. 1 Если новое значение расстояния от начальной вершины до проверяемой меньше старого значения, то в таблицу вносится найденное число, иначе расстояние не изменяется. 1 Решение повторяется до тех пор, пока не будут проверены все оставшиеся вершины. 1
• Метод потенциалов. 1 Произвольно выбранной вершине назначается нулевой потенциал, называемый началом отсчёта. 1 Затем определяют соседние с выбранной вершины и находят их потенциалы. 1 Из всех полученных потенциалов выбирается наименьший, и его значение присваивается текущей проверяемой вершине. 1 Расчёт ведётся до тех пор, пока не будут найдены потенциалы всех вершин графа. 1