Кратчайший путь (A, C, E, D, F) между вершинами A и F во взвешенном ориентированном графе.
Зада́ча о кратча́йшем пути́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для её решения. .
У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе.
Значимость данной задачи определяется её различными практическими применениями. Например, в GPS-навигаторах осуществляется поиск кратчайшего пути между точкой отправления и точкой назначения. В качестве вершин выступают перекрёстки, а дороги являются рёбрами, которые лежат между ними. Если сумма длин дорог между перекрёстками минимальна, тогда найденный путь самый короткий.
Содержание 1 Определение
2 Задача о кратчайшем пути с учётом дополнительных ограничений
3 Алгоритмы
4 Задача поиска кратчайшего пути из одной вершины во все остальные 4.1 Невзвешенный ориентированный граф
4.2 Ориентированный граф с неотрицательными весами
4.3 Ориентированный граф с произвольными весами 5 Задача о кратчайшем пути между всеми парами вершин
6 Применение 6.1 Картографические сервисы
6.2 Недетерминированная машина
6.3 Сети дорог 7 Похожие задачи
8 Постановка задачи линейного программирования
9 См. также
10 Примечания
11 Литература
Поиск оптимального пути в ненагруженном орграфе