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

 Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами 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. 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)+ a_y,x} (1)
   3. Если d(x)=∞ для всех неокрашенных вершин, то алгоритм заканчивается т. к. отсутствуют пути из вершины S в неокрашенные вершины. Иначе окрашивается та вершина, для которой величина d(x) является минимальной. Окрашивается и дуга, ведущая в эту вершину в соответствии с выражением (1) и полагаем y=x.
   4. Если y=t, кратчайший путь из s в t найден. Иначе переходим к шагу 2.

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

Пример