Зада́ча о кратча́йшем пути́ (англ. shortest path problem) — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь.
Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для ее решения[⇨].
У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе.
Значимость данной задачи определяется ее различными практическими применениями[⇨]. Например в GPS-навигаторах, где осуществляется поиск кратчайшего пути между двумя перекрестками. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Сумма расстояний всех дорог между перекрестками должна быть минимальной, тогда найден самый короткий путь.
Существуют различные постановки задачи о кратчайшем пути:
· Задача о кратчайшем пути в заданный пункт назначения. Требуется найти кратчайший путь в заданную вершину назначения t, который начинается в каждой из вершин графа (кроме t). Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине (в которой осуществляется поиск кратчайшего пути из заданной вершины во все остальные).
· Задача о кратчайшем пути между заданной парой вершин. Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.
· Задача о кратчайшем пути между всеми парами вершин. Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.
В различных постановках задачи, роль длины ребра могут играть не только сами длины, но и время, стоимость, расходы, объем затрачиваемых ресурсов (материальных, финансовых, топливно-энергетических и т. п.) или другие характеристики, связанные с прохождением каждого ребра. Таким образом, задача находит практическое применение в большом количестве областей (информатика, экономика, география и др.).
Алгоритм Дейкстры разработан для нахождения кратчайшего пути между заданным исходным узлом и любым другим узлом сети.
В процессе выполнения этого алгоритма при переходе от узла i к следующему узлу j используется специальная процедура пометки ребер. Обозначим через ui кратчайшее расстояние от исходного узла 1 до узла i, через dij - длину ребра (i, j). Тогда для узла j определим метку [uj, i] следующим образом:
[uj, i] = [ui + dij, i], dij >= 0
Метки узлов в алгоритме Дейкстры могут быть двух типов: временные и постоянные. Временная метка впоследствии может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Когда же станет очевидным, что не существует более короткого пути от исходного узла к данному, статус временной метки изменяется на постоянный
Вычислительная схема алгоритма состоит из следующих шагов.
Шаг i. а) Вычисляются временные метки [ui + dij, i] для всех узлов j, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [uj, k], полученную от другого узла k, и если ui + dij < uj, тогда метка [uj, k] заменяется на
[ui + dij, i].
b) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка [ur, s] с наименьшим значением расстояния ur среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем i = r и повторяем шаг i.
В результате выполнения алгоритма на каждом шаге получаем следующую таблицу меток:
Узел
Метка
Статус метки
Алгоритм позволяет проводить вычисления непосредственно по схеме сети, как показано на рисунке 1.
Пример. На рисунке 1 показана транспортная сеть, состоящая из пяти городов (расстояния между городами (в километ
аг 0. Назначаем узлу 1 постоянную метку [0, -].
Шаг 1. Из узла 1 можно достичь узлов 2 и 3. Вычисляем метки для этих узлов, в результате получаем следующую таблицу меток:
Узел Метка Статус метки
1 [0, -] Постоянная
2 [0 + 100, 1] = [100, 1] Временная
3 [0 + 30, 1] = [30, 1] <-Временная
Среди узлов 2 и 3 узел 3 имеет наименьшее значение расстояния (u3 = 30). Поэтому статус метки этого узла изменяется на "постоянная".
Шаг 2. Из узла 3 (последнего узла с постоянной меткой) можно попасть в узлы 4 и 5. Получаем следующий список узлов:
Узел Метка Статус метки
1 [0, -] Постоянная
2 [100, 1] Временная
3 [30, 1] Постоянная
4 [30 + 10, 3] = [40, 3] <-Временная
5 [30 + 60, 3] = [90, 3] Временная
Временный статус метки [40, 3] узла 4 заменяется на постоянный (u4 = 40).
Шаг 3. Из узла 4 можно достичь узлов 2 и 5. После вычисления меток получим следующий их список:
Узел Метка Статус метки
1 [0, -] Постоянная
2 [40 + 15, 4] = [55, 4] <-Временная
3 [30, 1] Постоянная
4 [40, 3] Постоянная
5 [90, 3] или [40 + 50, 4] = [90, 4] Временная
Временная метка [100, 1], полученная узлом 2 на втором шаге, изменена на [55, 4]. Это указывает на то, что найден более короткий путь к этому узлу (проходящий через узел 4). На третьем шаге узел 5 получает две метки с одинаковым значением расстояния u5 = 90.
Шаг 4. Из узла 2 можно перейти только в узел 3, но он уже имеет постоянную метку, которую нельзя изменить. Поэтому на данном шаге получаем такой же список меток, как и на предыдущем шаге, но с единственным изменением: метка узла 2 получает статус постоянной. С временной меткой остается только узел 5, но так как из этого узла нельзя попасть ни в какой другой, процесс вычислений заканчивается.
Алгоритм позволяет проводить вычисления непосредственно по схеме сети, как показано на рисунке 2.
Рис.2. Вычисления по схеме (в скобках указан номер шага
Кратчайший маршрут между узлом 1 и любым другим узлом определяется начиная с узла назначения путем прохождения их в обратном направлении с помощью информации, представленной в постоянных метках. Например, для определения кратчайшего маршрута между узлами 1 и 2 получаем такую обратную последовательность узлов:
Таким образом, получаем путь 1->3->4->2 общей длиной 55 километров.
Кратчайший маршрут между узлом 1 и любым другим узлом определяется начиная с узла назначения путем прохождения их в обратном направлении с помощью информации, представленной в постоянных метках
Например, для определения кратчайшего маршрута между узлами 1 и 2 получаем такую обратную последовательность узлов:
