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

Вариант 1. Дана сеть автомобильных дорог, соединяющих города Московской области. Некоторые дороги односторонние. Найти кратчайшие пути от города Москвы до каждого города области (если двигаться можно только по дорогам).

Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

Дан взвешенный ориентированный[1] граф ${\displaystyle G(V,E)}$ без дуг отрицательного веса[2]. Найти кратчайшие пути от некоторой вершины ${\displaystyle a}$ графа ${\displaystyle G}$ до всех остальных вершин этого графа.

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке.

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями — пути между ними (рёбра графа).

В кружках обозначены номера вершин, над рёбрами обозначен их вес — длина пути.

Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг.

Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна.

Длина пути в неё через вершину 1 равна сумме значения метки вершины 1 и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7.

Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.

Все соседи вершины 1 проверены.

Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит.

Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг.

Снова находим «ближайшую» из непосещённых вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед — вершина 3, так как имеет минимальную метку.

Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а это меньше 17, поэтому метка не меняется.

Ещё один сосед вершины 2 — вершина 4.

Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22).

Поскольку 22<${\displaystyle \infty }$, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещённую.

Третий шаг.

Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Дальнейшие шаги.

Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

Завершение выполнения алгоритма.

Алгоритм заканчивает работу, когда все вершины посещены.

Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

Если в какой-то момент все непосещённые вершины помечены бесконечностью, то это значит, что до этих вершин нельзя добраться (то есть граф несвязный). Тогда алгоритм может быть завершён досрочно.

• ${\displaystyle V}$ — множество вершин графа
• ${\displaystyle E}$ — множество рёбер графа
• ${\displaystyle w[ij]}$ — вес (длина) ребра ${\displaystyle ij}$
• ${\displaystyle a}$ — вершина, расстояния от которой ищутся
• ${\displaystyle U}$ — множество посещённых вершин
• ${\displaystyle d[u]}$ — по окончании работы алгоритма равно длине кратчайшего пути из ${\displaystyle a}$ до вершины ${\displaystyle u}$
• ${\displaystyle p[u]}$ — по окончании работы алгоритма содержит кратчайший путь из ${\displaystyle a}$ в ${\displaystyle u}$
• ${\displaystyle v}$ — текущая вершина, рассматриваемая алгоритмом

Присвоим

${\displaystyle d[a]\gets 0,\ p[a]\gets 0}$

Для всех ${\displaystyle u\in V}$ отличных от ${\displaystyle a}$ присвоим ${\displaystyle d[u]\gets \infty }$.

Пока ${\displaystyle \exists v\notin U}$. Пусть ${\displaystyle v\notin U}$ — вершина с минимальным ${\displaystyle d[v]}$ занесём ${\displaystyle v}$ в ${\displaystyle U}$

Для всех ${\displaystyle u\notin U}$ таких, что ${\displaystyle vu\in E}$

если ${\displaystyle d[u]>d[v]+w[vu]}$ то

изменим ${\displaystyle d[u]\gets d[v]+w[vu]}$

изменим ${\displaystyle p[u]\gets (p[v],u)}$

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

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

На каждом шаге цикла мы ищем вершину ${\displaystyle v}$ с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины ${\displaystyle u}$. Если в них (в ${\displaystyle u}$) расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 ${\displaystyle d[i]=\infty }$. Последний случай возможен тогда и только тогда, когда граф G несвязный.

Пусть ${\displaystyle l(v)}$ — длина кратчайшего пути из вершины ${\displaystyle a}$ в вершину ${\displaystyle v}$. Докажем по индукции, что в момент посещения любой вершины ${\displaystyle z}$ выполняется равенство ${\displaystyle d(z)=l(z)}$.

База. Первой посещается вершина ${\displaystyle a}$. В этот момент ${\displaystyle d(a)=l(a)=0}$.

Шаг. Пусть мы выбрали для посещения вершину ${\displaystyle z\neq a}$. Докажем, что в этот момент ${\displaystyle d(z)=l(z)}$. Для начала отметим, что для любой вершины ${\displaystyle v}$ всегда выполняется ${\displaystyle d(v)\geq l(v)}$ (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть ${\displaystyle P}$ — кратчайший путь из ${\displaystyle a}$ в ${\displaystyle z}$. Вершина ${\displaystyle z}$ находится на ${\displaystyle P}$ и не посещена. Поэтому множество непосещённых вершин на ${\displaystyle P}$ непусто. Пусть ${\displaystyle y}$ — первая непосещённая вершина на ${\displaystyle P}$, ${\displaystyle x}$ — предшествующая ей (следовательно, посещённая). Поскольку путь ${\displaystyle P}$ кратчайший, его часть, ведущая из ${\displaystyle a}$ через ${\displaystyle x}$ в ${\displaystyle y}$, тоже кратчайшая, следовательно ${\displaystyle l(y)=l(x)+w(xy)}$.

По предположению индукции, в момент посещения вершины ${\displaystyle x}$ выполнялось ${\displaystyle d(x)=l(x)}$, следовательно, вершина ${\displaystyle y}$ тогда получила метку не больше чем ${\displaystyle d(x)+w(xy)=l(x)+w(xy)=l(y)}$. Следовательно, ${\displaystyle d(y)=l(y)}$. Если ${\displaystyle z=y}$, то индукционный переход доказан. Иначе, поскольку сейчас выбрана вершина ${\displaystyle z}$, а не ${\displaystyle y}$, метка ${\displaystyle z}$ минимальна среди непосещённых, то есть ${\displaystyle d(z)\leq d(y)=l(y)\leq l(z)}$. Комбинируя это с ${\displaystyle d(z)\geq l(z)}$, имеем ${\displaystyle d(z)=l(z)}$, что и требовалось доказать.

Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент ${\displaystyle d=l}$ для всех вершин.

Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещённых вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество рёбер в графе G.

• В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается всё множество вершин, а для хранения величин d используется массив, время работы алгоритма есть ${\displaystyle O(n^{2})}$. Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма ${\displaystyle O(n^{2}+m)}$, но, так как ${\displaystyle m\leq n(n-1)}$, оно составляет ${\displaystyle O(n^{2})}$.

• Для разреженных графов (то есть таких, для которых m много меньше n²) непосещённые вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время удаления вершины из ${\displaystyle {\overline {U}}}$ станет ${\displaystyle \log n}$ при том, что время модификации ${\displaystyle d[i]}$ возрастёт до ${\displaystyle \log n}$. Так как цикл выполняется порядка n раз, а количество смен меток не больше m, время работы такой реализации — ${\displaystyle O(n\log n+m\log n)}$.

• Если для хранения непосещённых вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за ${\displaystyle O(\log n)}$, а уменьшение значения в среднем за ${\displaystyle O(1)}$, то время работы алгоритма составит ${\displaystyle O(n\log n+m)}$. Однако согласно лекциям Алексеева и Таланова[3]:

скрытые константы в асимптотических оценках трудоёмкости велики и использование фибоначчиевых куч редко оказывается целесообразным: обычные двоичные (d-ичные) кучи на практике эффективнее.

Альтернативами им служат толстые кучи, тонкие кучи и кучи Бродала, обладающие теми же асимптотическими оценками, но меньшими константами[4].