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

Описание

В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U — массив булевых переменных.

В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (бо́льшим максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.

На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 . Последний случай возможен тогда и только тогда, когда граф G не связан.

Алгоритм Дейкстры реализуется как последовательность следующих шагов:

1. Положить l(s)=0 и l(i)=∞ для всех v_i≠s. Окрасить s  и положить p=s.
2. Для всех неокрашенных вершин выполнить проверку:

если l(p)+w(p,i)<l(i), то l(i)=l(p)+w(p,i) и θ(i)=p.

1. Если теперь для всех неокрашенных вершин l(i)=∞, то перейти к шагу 5, так как из s нет путей в неокрашенные вершины. Иначе окрасить вершину с наименьшей меткой l(k) и дугу (θ(k),k); перейти к шагу 4.
2. Если p=f, то перейти к шагу 5, иначе перейти к шагу 2.
3. Закончить выполнение алгоритма.