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

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

Формальное описание

В строке 1 производится обычная инициализация величин d и pi, а в строке 2 инициализируется пустое множество вершин S. В этом алгоритме поддерживается инвариант, согласно которому в начале каждой итерации цикла while в строках 4-8 выполняется равенство Q = V — S. В строке 3 неубывающая очередь с приоритетами Q инициализируется таким образом, чтобы она содержала все вершины множества V; поскольку в этот момент S = 0, после выполнения строки 3 сформулированный выше инвариант выполняется. При каждой итерации цикла while в строках 4-8 вершина и извлекается из множества Q = V — S и добавляется в множество 5, в результате чего инвариант продолжает соблюдаться. (Во время первой итерации этого цикла u = s.) Таким образом, вершина и имеет минимальную оценку кратчайшего пути среди всех вершин множества V — 5. Затем строках 7-8 ослабляются все ребра (u, v), исходящие из вершины и. Если текущий кратчайший путь к вершине v может быть улучшен в результате прохождения через вершину и, выполняется ослабление и соответствующее обновление оценки величины d [v] и предшественника тг [v]. Обратите внимание, что после выполнения строки 3 вершины никогда не добавляются в множество Q и что каждая вершина извлекается из этого множества и добавляется в множество 5 ровно по одному разу, поэтому количество итераций цикла while в строках 4-8 равно | V|. Поскольку в алгоритме Дейкстры из множества V — S для помещения в множество 5 всегда выбирается самая "легкая" или "близкая" вершина, говорят, что этот алгоритм придерживается жадной стратегии.

Оценка сложности     [вверх]

Время выполнения алгоритма Дейкстры зависит от реализации неубывающей очереди с приоритетами. Сначала рассмотрим случай, когда неубывающая очередь с приоритетами поддерживается за счет того, что все вершины пронумерованы от 1 до |V|. Атрибут d[v] просто помещается в элемент массива с индексом v. Каждая операция Insert и Decrease_Key (неявно присутствует в процедуре Relax) занимает время 0(1), а каждая операция Extract_Min — время О (V) (поскольку в ней производится поиск по всему массиву); в результате полное время работы алгоритма равно О (V² + Е) = О(V²).

Если граф достаточно разреженный, в частности, если количество вершин и ребер в нем связаны соотношением Е = o(V²/lgV), с практической точки зрения целесообразно реализовать неубывающую очередь с приоритетами в виде бинарной неубывающей пирамиды. (важная деталь реализации заключается в том, что вершины и соответствующие им элементы пирамиды должны поддерживать идентификаторы друг друга.) Далее, каждая операция Extract_Min занимает время О (lg V), Как и раньше, таких операций |V|. Время, необходимое для построения неубывающей пирамиды, равно O(V). Каждая операция Decrease_Key занимает время O(lgV), и всего выполняется не более |Е| таких операций. Поэтому полное время выполнения алгоритма равно О ((V + Е) lg V), что равно О (Е*lg V), если все вершины достижимы из истока. Это время работы оказывается лучшим по сравнению со временем работы прямой реализации О (V²), если Е = о (V²/lg V).

Пример работы алгоритма     [вверх]

Визуализатор для алгоритма Дейкстры.