Некоторые методы решения задач на сокращение пути:

• Алгоритм Дейкстры. 1 Находит кратчайший путь от одной из вершин графа до всех остальных. 1 Работает только для графов без рёбер отрицательного веса. 1
• Алгоритм Беллмана — Форда. 1 Находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. 1 Вес рёбер может быть отрицательным. 1
• Алгоритм поиска A*. 1 Находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе. 1
• Алгоритм Флойда — Уоршелла. 1 Находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа. 1
• Алгоритм Ли (волновой алгоритм). 1 Основан на методе поиска в ширину. 1 Находит путь между вершинами графа, содержащий минимальное количество промежуточных вершин (рёбер). 1
• Метод ветвей и границ. 34 Применяется для точного или приближённого решения задач, в том числе задачи коммивояжёра. 34
• Метод Кларка-Райта. 4 Относится к числу приближённых, итерационных методов и может использоваться для компьютерного решения задачи развозки. 4 Погрешность решения не превосходит в среднем 5–10%. 4