Комбинаторные алгоритмы для программистов



             

Алгоритм Дейкстры нахождения кратчайшего пути


Рассмотрим алгоритм нахождения путей в ориентированном графе. Пусть есть ориентированный граф

G(V,E)
, у которого все дуги имеют неотрицательные метки (веса дуг), а одна вершина определена как источник. Задача состоит в нахождении весов кратчайших путей от источника ко всем другим вершинам граф
G(V,E)
. Здесь длина пути определяется как сумма весов дуг, составляющих путь. Эта задача часто называется задачей нахождения кратчайшего пути с одним источником. Отметим, что мы будем говорить о длине пути даже тогда, когда она измеряется в других, не линейных, единицах измерения, например, во временных единицах или в денежном эквиваленте.

Можно представить орграф

G(V,E)
в виде карты маршрутов рейсовых полетов из одного города в другой. Каждая вершина соответствует городу, а ребро (дуга)
(v,w)
- рейсовому маршруту из города
v
в город
w
. Вес дуги
(v,w)
- это время полета из города
v
в город
w
. В этом случае решение задачи нахождения кратчайшего пути с одним источником для ориентированного графа трактуется как минимальное время перелета между различными городами.

Для решения поставленной задачи будем использовать "жадный" алгоритм, который называют алгоритмом Дейкстры (Dijkstra). Алгоритм строит множество

S
вершин, для которых кратчайшие пути от источника уже известны. На каждом шаге к множеству
S
добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. Если веса всех дуг неотрицательны, то можно быть уверенным, что кратчайший путь от источника к конкретной вершине проходит только через вершины множество
S
. Назовем такой путь особым. На каждом шаге алгоритма используется также массив
M
, в который записываются длины кратчайших особых путей для каждой вершины. Когда множество
S
будет содержать все вершины орграфа, то есть для всех вершин будут найдены особые пути, тогда массив
M
будет содержать длины кратчайших путей от источника к каждой вершине.




Содержание  Назад  Вперед