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

• Алгоритм Дейкстры. 12 На каждом шаге выбирает из множества непросмотренных вершин вершину с наименьшим расстоянием до старта и релаксирует рёбра, исходящие из неё. 1 Завершает работу, когда цель достигнута (или просмотрены все вершины). 1
• Двухэтапные алгоритмы. 1 Состоят из препроцессинга (запускается единожды для графа, может занимать много времени, рассчитывает вспомогательную информацию) и запроса (запускается по требованию для пары вершин, должен выполняться очень быстро). 1 Например, алгоритм ALT (A* + ориентиры + неравенство треугольника). 1
• Эвристические методы. 5 В большинстве из них находится не самый эффективный маршрут, а приближённое решение. 5 Например, жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешёвого включения), метод минимального остовного дерева. 5 На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов. 5
• Прямой симметричный алгоритм. 5 Применяется для нахождения кратчайшего разомкнутого пути. 5 Суть алгоритма в том, что начиная от стартовой вершины рассматриваются альтернативные пути движения к вершине финиша. 5 Если при рассмотрении альтернативных путей нарушается принцип симметричности, то «несимметричный» путь отбрасывается. 5