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

Задание.

Найти кратчайшее расстояние между вершинами S (7) и T (8) c помощью алгоритма Дейкстры.

 

 

Начальная и конечная вершины в программе выделяются оранжевым цветом.

 

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

Алгоритм Дейкстры находит кратчайшее расстояние от одной вершины графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса.

 

1. Присвоение начальных значений.

Приписываем вершине S постоянную метку d(S) = 0, а всем остальным вершинам x ∈ V, отличным от S, временные метки d(x) = ∞.

Положим y = S, где y — последняя из вершин, получивших постоянную метку.

 

2. Обновление пометок.

Для всех вершин x, смежных с y и не имеющих постоянной метки, пересчитаем величины d(x) по следующей формуле:

d(x) = min { d(x), d(y) + a(y, x) }

Если d(x) = ∞ для всех непомеченных вершин x, закончить процедуру алгоритма: в исходном графе отсутствуют пути из S в помеченные вершины.

В противном случае переходим к шагу 3.

 

3. Выбор вершины с наименьшей меткой.

Выбрать ту из вершин x, которая имеет наименьшую временную метку, т.е. ту, для которой величина d(x) является наименьшей.

 

4. Превращение метки в постоянную.

Положим y = x — вершина графа с наименьшей временной меткой, которой присваивается постоянная метка.

 

5. Проверка результата.

Если y = T, закончить процедуру. Кратчайший путь из вершины S в вершину T найден. Это единственный путь из S в T, составленный из помеченных дуг.

Если y≠x, перейти к шагу 2.