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

Алгоритм Дейкстры – алгоритм на графах, изобретенный нидерландским ученым Э.Дейкстрой в 1959 году. Алгоритм находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса. Широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPFи IS-IS.

Каждой вершине сопоставляется метка – минимальное известное расстояние от этой вершины до а. Алгоритм работает пошагово – на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как не посещённые.

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

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

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

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

Рисунок 1. Блок-схема алгоритма