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

Шаг 1. Полагаем S=V\{v₀}, d[v_i] =a(v₀, v_i) для всех i=1,…,k.

Шаг 2. Если |S| = 1, то выполнить шаг 4. Выбрать в S элемент v*, для которого величина d[v*] является наименьшей (среди всех элементов из S).

Шаг 3. Положить S=S\{v*}, d[v] =min{d[v], d[v*]+d[v*®v]} "vÎS и перейти к шагу 2.

Шаг 4. Выдать d(v₁),…,d(v_k). Конец работы алгоритма.

Алгоритм осуществляет «итерративный» процесс нахождения расстояния d(v_i) для i=1,…,k. Проследим, как это делается для сети N, изображенной на рис. 6.12. Работа алгоритма будет иллюстрироваться заполнением таблицы 6.1.

При выполнении первого шага алгоритма величины d(v_i) примут значения, которые указаны в нулевой строке таблицы. Из них точным является только d(v₂), значения остальных величин завышены. На шаге 2 в качестве v’ выбирается вершина v₂ (в таблице соответствующее значение набрано жирным шрифтом) и удаляется из S на шаге 3. На том же шаге уточняются предыдущие значения d(v) для vÎS (см. первую строку таблицы 6.1). На этом первый проход алгоритма заканчивается. На втором проходе в качестве v’ берется v₅, удаляется из S и значения d(v) для vÎS снова уточняются. Результат уточнения отражен во второй строке таблицы. Когда множество S будет содержать только вершину V₃, алгоритм заканчивает работу. Результат: d(v₁)=3, d(v₂)=1, d(v₃)=4, d(v₄)=4, d(v₅)=3.

Поскольку на каждом проходе алгоритма число элементов множества S уменьшается на единицу, то алгоритм Дейкстры всегда заканчивает работу. Следующее утверждение показывает, что он выдает «то что нужно».

Теорема. Пусть для сети N и фиксированной вершины v₀ этой сети алгоритм Дейкстры выдал величины d(v₁),…,d(v_k). Тогда d(v_i) есть расстояние от v₀ до v_i для i=1,…,k.

Доказательство. Отметим вначале, что если d(v_i)¹ ¥, то величина d(v_i) равна длине некоторого пути из v₀ в v_i. Пусть в очередном проходе алгоритма на втором шаге выбирается вершина v’, d(v’) ¹ ¥ и

v₀=x₀, x₁,…,x_i-1,x_i,…,x_p-1, x_p=v’ –

кратчайший (v₀,v’)–путь. Убедимся в том, что для любой вершины х этого пути выполняется равенство d(x)=d₀(v₀,x). Действительно, для х=х₀ это справедливо. Предположим, что d(x_i-1)=d(v₀,x), но d(x_i)>d(v₀,x_i). Тогда поскольку d(x_i-1)<d(v’), то вершина х_i-1 выбиралась на втором шаге в более раннем проходе алгоритма. На третьем шаге этого прохода d(x_i) получило бы значение d(x_i-1)+a(x_i-1,x_i), которое равно d(v₀,x_i). Следовательно, для любой вершины х фиксированного пути выполняется равенство d(x)=d(v₀,x), в частности, d(v’)=d(v₀,v’). Отсюда следует, что если существует (v₀,v)–путь в сети N, то на момент завершения работы алгоритма выполняется равенство d(v)=d(v₀,v).