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

Основная идея алгоритма Дейкстры

Граф представляет собой набор точек, называемых вершинами графа, и соединяющих их линий, называемых рёбрами.

Кратчайший путь между вершинами – это путь минимально возможной длины, соединяющий на графе одну вершину с другой.

Длина пути – это сумма длин всех дуг (ориентированных рёбер – рёбер с чётко указанными началом и концом), по которым проходит этот путь.

Длины дуг, называемые ещё весовыми коэффициентами, предполагаются известными. Если в графе нет дуги, соединяющей некоторые две отдельные вершины, то её длина условно считается равной бесконечности.

Понятно, что для любых двух вершин произвольного графа могут существовать сразу несколько путей, соединяющих их. Чтобы найти кратчайший из этих путей будем придерживаться специальной стратегии, действуя согласно алгоритму, разработанному нидерландским учёным Дейкстрой.

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

Помеченная на каждом этапе новая вершина (та, до которой путь оказался кратчайшим) становится определяющей для следующего шага. И этот построенный до неё кратчайший путь закрашивается.

Повторяя данные действия, последовательно просматривая и поочерёдно отмечая вершины графа, в итоге добираемся до конечного пункта. Те рёбра графа, которые в результате оказались закрашенными (вместе с отмеченными их крайними точками), образуют ориентированное дерево кратчайших путей (с корнем в исходной вершине графа). Далее остаётся выбрать на нём путь, который соединяет начальную точку с конечной. Это и будет искомый путь.

Пример поиска кратчайшего пути по алгоритму

Рассмотрим применение алгоритма Дейкстры к конкретному примеру. Пусть задан граф, представленный на рисунке:

Рисунок 1. Граф. Автор24 — интернет-биржа студенческих работ

Перед началом выполнения алгоритма все вершины и дуги на графе не раскрашены. Нужно найти и закрасить кратчайший путь от вершины $s$ до вершины $t$.

Для этого на каждом шаге по определённым правилам строятся пути, ведущие от начальной вершины $s$ до всех неотмеченных на графе вершин (обозначаемых здесь $y$), и далее из этих маршрутов выбирается условно кратчайший путь.

При переходе к каждой следующей итерации алгоритма среди всех непомеченных точек на графе отмечается та вершина (обозначается буквой $x$), до которой путь из вершины $s$ оказался самым коротким на этом шаге.

Каждый раз длина пути пересчитывается по формуле:

$S(y) = min\{S(y), S(x) + r(x,y)\}$,

где:

• $r(x,y)$ – вес дуги, соединяющей вершины $x$ и $y$,
• $S(y)$ – длина пути, соединяющего начальную точку $s$ с вершиной $y$.

Применим теперь данный алгоритм к графу, изображённому на рисунке.

1. Поскольку, очевидно, $S(s) = 0$ – самое короткое расстояние на графе (от стартовой точки $s$ до неё же), то отмечаем вершину $s$. При этом изначально считается, что $S(y) = ∞$ для всех остальных (отличных от $s$) вершин заданного графа.

2. Согласно алгоритму полагаем, что $x = s$. И далее вычисляем величины $S(y)$ для всех непомеченных вершин графа:

   $S(a) = min\{S(a), S(s) + r(s, a)\} = min\{∞,0 + 5\} = 5, $

   $S(b) = min\{S(b), S(s) + r(s, b)\} = min\{∞,0 + ∞\} = ∞, $

   $S(c) = min\{S(c), S(s) + r(s, c)\} = min\{∞,0 + 2\} = 2, $

   $S(d) = min\{S(d), S(s) + r(s, d)\} = min\{∞,0 + 7\} = 7, $

   $S(t) = min\{S(t), S(s) + r(s, t)\} = min\{∞,0 + ∞\} = ∞. $

   Выбираем среди полученных величин минимальную. В данном случае это $S(c) = 2$. Поэтому отмечаем вершину $c$ и закрашиваем дугу $(s,c)$, которая соответствует кратчайшему пути с длиной $S(c)$.

3. Продолжаем далее, пока не пройдём по графу до конечного пункта – вершины $t$. Сейчас оказалось, что $x = c$. И теперь по формуле пересчитываем величины $S(y)$ для ещё не отмеченных вершин:

   $S(a) = min\{S(a), S(c) + r(c, a)\} = min\{5,2 + ∞\} = 5, $

   $S(b) = min\{S(b), S(c) + r(c, b)\} = min\{∞,2 + 5\} = 7, $

   $S(d) = min\{S(d), S(c) + r(c, d)\} = min\{7,2 + 4\} = 6, $

   $S(t) = min\{S(t), S(c) + r(c, t)\} = min\{∞,2 + ∞\} = ∞ $

   Так как величина $S(a) = 5$ является минимальной из всех полученных на этом шаге величин, то отмечаем вершину $a$ и закрашиваем на графе дугу $(s,a)$, которая и определяет величину $S(a)$.

4. Аналогично предыдущему шагу за точку $x$ принимаем только что помеченную точку: $x = a$. Снова пересчитываем величины $S(y)$ для оставшихся вершин:

   $S(b) = min\{S(b), S(a) + r(a, b)\} = min\{7,5 + 3\} = 7, $

   $S(d) = min\{S(d), S(a) + r(a, d)\} = min\{6,5 + ∞\} = 6, $

   $S(t) = min\{S(t), S(a) + r(a, t)\} = min\{∞,5 + ∞\} = ∞. $

   Поскольку величина $S(d) = 6$ оказалась здесь наименьшей, то отмечаем вершину $d$ и закрашиваем дугу $(c,d)$, определяющую эту величину $S(d)$.

5. Получили, что $x = d$. Теперь по формуле вычисляем величины:

   $S(b) = min\{S(b), S(d) + r(d, b)\} = min\{7,6 + ∞\} = 7, $

   $S(t) = min\{S(t), S(d) + r(d, t)\} = min\{∞,6 + 2\} = 8. $

   Так как величина $S(b) = 7$ меньше величины $S(t)$, то на этом шаге помечаем вершину $b$ и закрашиваем дугу $(c,b)$, соответствующую выбранному кратчайшему расстоянию.

6. И теперь последняя итерация алгоритма. Здесь $x = b$ и расстояние

   $S(t) = min\{S(t), S(b) + r(b, t)\} = min\{8,7 + 2\} = 8. $

   Наконец, вершина $t$ достигнута. Отмечаем её и закрашиваем кратчайший путь, ведущий к ней на этом шаге – дугу $(d,t)$.

В итоге, после применения алгоритма Дейкстры, мы получили дерево кратчайших путей, состоящее из дуг $(s,c), (s,a), (c,d), (c,b)$ и $(d,t)$:

Рисунок 2. Дерево кратчайших путей. Автор24 — интернет-биржа студенческих работ

Из них единственный кратчайший путь, соединяющий вершину $s$ с вершиной $t$, проходит по дугам $(s,c), (c,d), (d,t)$ и имеет длину $2 + 4 + 2 = 8$.

Пошаговое описание алгоритма Дейкстры

Теперь запишем в общей форме те действия, которые были выполнены в примере при отыскании кратчайшего пути. Это позволит в дальнейшем применять данный алгоритм для решения любой задачи такого же типа.

Перечислим шаги алгоритма Дейкстры по пунктам:

1. На графе каждой вершине $y$ ставится в соответствие число $S(y)$, которое вычисляется как длина условно кратчайшего пути из начальной точки $s$ в вершину $y$. При этом рассматриваются только пути, проходящие через уже помеченные вершины. Изначально полагается, что $S(s) = 0$ и $S(y) = ∞$ для любой (отличной от $s$) вершины $y$. Отмечается вершина $s$, и поэтому переменная $x = s$.
2. Для каждой неотмеченной вершины $y$ заданного графа пересчитывается величина $S(y)$ по следующей формуле: $S(y) = min\{S(y), S(x) + r(x,y)\}$, где $x$ – промежуточная вершина, отмеченная на предыдущем шаге. Данная формула позволяет выбрать наиболее короткий путь от начальной точки графа до нужной вершины, сравнивая величину пути $S(y)$ с длиной пути, составленного из нескольких дуг и включающего при этом помеченную вершину $x$.

3. Далее возможны следующие варианты:

   • Если $S(y) = ∞$ для всех неотмеченных вершин $y$, то отсутствуют пути из $s$ в оставшиеся вершины графа и требуется закончить процедуру алгоритма.
   • Иначе пометить на графе ту вершину $y$, для которой величина $S(y)$ оказалась минимальной, а также закрасить дугу, оптимально приводящую в эту вершину $y$. Далее полагаем, что $x = y$.

4. Если оказалось, что $x = t$, то алгоритм завершён, и в результате его применения найден искомый кратчайший путь (это единственный путь из вершины $s$ в вершину $t$, который в ходе выполнения алгоритма получился на графе закрашенным). Иначе требуется перейти к пункту 2 алгоритма и снова повторять его действия до тех пор, пока не будет получен кратчайший путь, соединяющий вершины $s$ и $t$.

Напомним, что данный метод поиска кратчайшего пути применим только для графов с неотрицательными весами дуг.