Алгоритм Дейкстры нахождения кратчайшего пути
Рассмотрим алгоритм нахождения путей в ориентированном графе. Пусть есть ориентированный граф
, у которого все дуги имеют неотрицательные метки (веса дуг), а одна вершина определена как источник. Задача состоит в нахождении весов кратчайших путей от источника ко всем другим вершинам граф
. Здесь длина пути определяется как сумма весов дуг, составляющих путь. Эта задача часто называется задачей нахождения кратчайшего пути с одним источником. Отметим, что мы будем говорить о длине пути даже тогда, когда она измеряется в других, не линейных, единицах измерения, например, во временных единицах или в денежном эквиваленте.
Можно представить орграф
в виде карты маршрутов рейсовых полетов из одного города в другой. Каждая вершина соответствует городу, а ребро (дуга)
- рейсовому маршруту из города
в город
. Вес дуги
- это время полета из города
в город
. В этом случае решение задачи нахождения кратчайшего пути с одним источником для ориентированного графа трактуется как минимальное время перелета между различными городами.
Для решения поставленной задачи будем использовать "жадный" алгоритм, который называют алгоритмом Дейкстры (Dijkstra). Алгоритм строит множество
вершин, для которых кратчайшие пути от источника уже известны. На каждом шаге к множеству
добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. Если веса всех дуг неотрицательны, то можно быть уверенным, что кратчайший путь от источника к конкретной вершине проходит только через вершины множество
. Назовем такой путь особым. На каждом шаге алгоритма используется также массив
, в который записываются длины кратчайших особых путей для каждой вершины. Когда множество
будет содержать все вершины орграфа, то есть для всех вершин будут найдены особые пути, тогда массив
будет содержать длины кратчайших путей от источника к каждой вершине.
Содержание раздела
