Главная|Решения онлайн |Теория | Основные формулы и обозначения |Обратная связь |


Алгоритм Дейкстры

 Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами s и t при положительных длинах дуг. Этот алгоритм,. предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи.
Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны m вершин, ближайших к вершине s (близость любой вершины x к вершине s определяется длиной кратчайшего пути, ведущего из s в x). Пусть также известны сами кратчайшие пути, соединяющие вершину s с выделенными m вершинами). Покажем теперь, как может быть определена (m + 1)-я ближайшая к s вершина.
Окрасим вершину s и m ближайших к ней вершин. Построим для каждой неокрашенной вершины y пути, непосредственно соединяющие с помощью дуг (х, у) каждую окрашенную вершину х с у. Выберем из этих путей кратчайший, и будем считать его условно кратчайшим путем из вершины s в вершину y.
Какая же из неокрашенных вершин является (m + 1)-й ближайшей к s вершиной? Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины s в (m +1)-ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т. е. вершины, входящие в число m вершин, ближайших к вершине s.
Итак, если известны m ближайших к s вершин, то (m + 1)-я ближайшая к s вершина может быть найдена так, как это описано выше. Начиная с m = 0, описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины s к вершине t.
Имея в виду приведенные соображения, мы можем теперь формально описать алгоритм Дейкстры.

 

Алгоритм

  1. Каждой вершине X в ходе алгоритма присваивается число d(x), равное длине кратчайшего пути из вершины S в вершину X и включающем только окрашенные вершины. Положить d(s)=0 и d(x)=∞ для всех остальных вершин графа. Окрашиваем вершину S и полагаем y=S, где y – последняя окрашенная вершина.
  2. Для каждой неокрашенной вершины X пересчитывается величина d(x) по следующей формуле:

    d(x)=min{d(x); d(y)+ ay,x} (1)

  3. Если d(x)=∞ для всех неокрашенных вершин, то алгоритм заканчивается т. к. отсутствуют пути из вершины S в неокрашенные вершины. Иначе окрашивается та вершина, для которой величина d(x) является минимальной. Окрашивается и дуга, ведущая в эту вершину в соответствии с выражением (1) и полагаем y=x.
  4. Если y=t, кратчайший путь из s в t найден. Иначе переходим к шагу 2.

     Каждый раз окрашивается вершина и дуга, заходящая в эту вершину. Окрашенные дуги не могут образовывать цикл, а образуют в исходном графе дерево с корнем (началом) в вершине s. Это дерево называют ориентированным деревом кратчайших путей. Путь из s в t принадлежит этому дереву. При поиске одного кратчайшего пути процедура наращивания завершается при достижении конечной вершины этого пути. Нам же необходимо получить все кратчайшие пути начинающиеся в вершине №1. Для этого процедуру наращивания ориентированного дерева продолжается до тех пор, пока все вершины не будут включены. Таким образом, мы получаем ориентированное дерево кратчайших путей, которое является покрывающим деревом графа.
Иногда в графе имеются несколько кратчайших путей. Кратчайший путь будет единственным, если в алгоритме ни разу не возникает неоднозначность при окрашивании дуги.

Отметим, что главным условием успешного применения алгоритма дейкстры к задаче на графе является неотрицательность длин дуг этого графа

Пример

Назад



R336709263964 - WebMoney 41001419134483 - Яндекс Деньги
WebMoneyПонравился сайт? Окажите помощь в развитиияндекс