Для определения оптимальных маршрутов в графах используют различные алгоритмы, которые решают задачу о кратчайшем пути. 23

Некоторые из них:

• Алгоритм Дейкстры. 12 Находит кратчайший путь от одной из вершин графа до всех остальных. 2 Работает только для графов без рёбер отрицательного веса. 2
• Алгоритм Беллмана — Форда. 23 Определяет самый короткий маршрут от одной точки графа ко всем другим точкам во взвешенном графе. 3 Вес рёбер может быть отрицательным. 2
• Алгоритм поиска A*. 2 Находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной). 2
• Алгоритм Флойда — Уоршелла. 23 Находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа. 23
• Алгоритм Джонсона. 23 Находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. 23
• Алгоритм Ли (волновой алгоритм). 23 Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (рёбер). 2

В разных постановках задачи в качестве веса ребра могут фигурировать не только меры длины, но и цена, временные интервалы, ресурсы и так далее. 3