Алгоритм дейкстры пример. Алгоритм дейкстры нахождения кратчайшего пути
Алгоритм Дейкстры – алгоритм на графах, который находит кратчайший путь между двумя данными вершинами в графе с неотрицательными длинами дуг. Также часто ставится задача расчёта кратчайшего пути от данной вершины до всех остальных. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации.
Описание
На вход алгоритма подаётся взвешенный ориентированный граф с дугами неотрицательного веса. На выходе получается набор кратчайших путей от данной вершины до других.
В начале расстояние для начальной вершины полагается равным нулю, а расстояния до всех остальных понимаются бесконечными. Массив флагов, обозначающих то, пройдена ли вершина, заполняется нулями. Затем на каждом шаге цикла ищется вершина с минимальным расстоянием до изначальной и флагом равным нулю. Для неё устанавливается флаг и проверяются все соседние вершины. Если рассчитанное ранее расстояние от исходной вершины до проверяемой больше, чем сумма расстояния до текущей вершины и длины ребра от неё до проверяемой вершины, то расстояние до проверяемой вершины приравниваем к расстоянию до текущей+ребро от текущей до проверяемой. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда расстояние до всех вершин c флагом 0 бесконечно. Последний случай возможен тогда и только тогда, когда граф несвязеный.
Алгоритм Дейкстры в псевдокоде
Вход: С : array of real – матрица длин дуг графа; s – вершина, от которой ищется кратчайший путь и t – вершина, к которой он ищется.
Выход: векторы Т: array of real; и Н: array of 0..р. Если вершина v лежит на кратчайшем пути от s к t, то T[v] - длина кратчайшего пути от s к у; Н[у] - вершина, непосредственно предшествующая у на кратчайшем пути.
Н – массив, в котором вершине n соответствует вершина m, предыдущая на пути к n от s.
T – массив, в котором вершине n соответствует расстояние от неё до s.
X – массив, в котором вершине n соответствует 1, если путь до неё известен, и 0, если нет.
инициализация массивов:
for v from 1 to р do
Т[ v ]: = ∞ { кратчайший путь неизвестен }
X[v]: = 0 { все вершины не отмечены}
H[s]: = 0 { s ничего не предшествует }
T[s] : = 0 { кратчайший путь имеет длину 0...}
X[s] : = 1 { ...и он известен } v : = s { текущая вершина }
М: { обновление пометок }
for и ∈ Г(и ) do
if Х[и] = 0 & Т[и] > T[v] + C then
Т[и] : = T[v] + C { найден более короткий путь из s в и через v }
H[u]: = v { запоминаем его }
m : = ∞
v : = 0
{ поиск конца кратчайшего пути }
for и from 1 to p do
if X[u] = 0 &T[u] < t then
v: = u ;
m: = T[u] { вершина v заканчивает кратчайший путь из s
if v = 0 then
stop { нет пути из s в t } end if
if v = t then
stop { найден кратчайший путь из s в t } end if
X[v]: = 1 { найден кратчайший путь из s в v } goto M
Обоснование
Для доказательства корректности алгоритма Дейкстры достаточно заметить, что при каждом выполнении тела цикла, начинающегося меткой М, в качестве v используется вершина, для которой известен кратчайший путь из вершины s. Другими словами, если X[v] = 1, то T[v] = d(s,v), и все вершины на пути (s,v), определяемом вектором Н, обладают тем же свойством, то есть
Vu Т[и] = 1 => Т[и] = d(s,u)&T] = 1.
Действительно (по индукции), первый раз в качестве v используется вершина s, для которой кратчайший путь пустой и имеет длину 0 (непустые пути не могут быть короче, потому что длины дуг неотрицательны). Пусть Т[u] = d(s,u) для всех ранее помеченных вершин и. Рассмотрим вновь помеченную вершину v , которая выбрана из условия T[v] = min Т[и]. Заметим, что если известен путь, проходящий через помеченные вершины, то тем самым известен кратчайший путь. Допустим (от противного), что T[v]> d(s, v), то есть найденный путь, ведущий из s в v, не является кратчайшим. Тогда на этом пути должны быть непомеченные вершины. Рассмотрим первую вершину w на этом пути, такую что T[w]= 0.Имеем: T[w]= d(s,w)⩽d(s>v) < Т[v],что противоречит выбору вершины u.
Временная сложность
Сложность алгоритма Дейкстры зависит от способа нахождения не посещённой вершины с минимальным расстоянием до изначальной, способа хранения множества непосещённых вершин и способа обновления меток. Пусть n количество вершин, а через m - количество рёбер в графе. Тогда в простейшем случае, когда для поиска вершины с минимальным расстоянием до изначальной вершины просматривается всё множество вершин, а для хранения расстояний используется массив, время работы алгоритма - О(n 2). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма O(n 2 +m), но, так как m много меньше n(n-1), в конечном счёте получается О(n 2).
Для разреженных графов (то есть таких, для которых m много меньше n²) непосещённые вершины можно хранить в двоичной куче, а в качестве ключа использовать значения расстояний. Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, время работы такой реализации - О(nlogn+mlogn)
Пример
Вычисление расстояний от вершины 1 по проходимым вершинам:
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Поиск кратчайшего пути ведется между двумя заданными вершинами в графе. Результатом является путь , то есть последовательность вершин и ребер, инцидентных двум соседним вершинам, и его длина .
Рассмотрим три наиболее эффективных алгоритма нахождения кратчайшего пути :
- алгоритм Дейкстры ;
- алгоритм Флойда ;
- переборные алгоритмы.
Указанные алгоритмы легко выполняются при малом количестве вершин в графе. При увеличении их количества задача поиска кратчайшего пути усложняется.
Алгоритм Дейкстры
Данный алгоритм является алгоритмом на графах, который изобретен нидерландским ученым Э. Дейкстрой в 1959 году. Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных и работает только для графов без ребер отрицательного веса.
Каждой вершине приписывается вес – это вес пути от начальной вершины до данной. Также каждая вершина может быть выделена. Если вершина выделена, то путь от нее до начальной вершины кратчайший, если нет – то временный. Обходя граф , алгоритм считает для каждой вершины маршрут , и, если он оказывается кратчайшим, выделяет вершину. Весом данной вершины становится вес пути. Для всех соседей данной вершины алгоритм также рассчитывает вес , при этом ни при каких условиях не выделяя их. Алгоритм заканчивает свою работу, дойдя до конечной вершины, и весом кратчайшего пути становится вес конечной вершины.
Алгоритм Дейкстры
Шаг 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине – 0.
Шаг 2. Все вершины не выделены.
Шаг 3. Первая вершина объявляется текущей.
Шаг 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра , соединяющего текущую вершину с невыделенной.
Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход . Иначе, текущей становится найденная вершина . Она же выделяется.
Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.
Шаг 7. Переход на шаг 4.
В программной реализации алгоритма Дейкстры построим множество S вершин, для которых кратчайшие пути от начальной вершины уже известны. На каждом шаге к множеству S добавляется та из оставшихся вершин, расстояние до которой от начальной вершины меньше, чем для других оставшихся вершин. При этом будем использовать массив D , в который записываются длины кратчайших путей для каждой вершины. Когда множество S будет содержать все вершины графа , тогда массив D будет содержать длины кратчайших путей от начальной вершины к каждой вершине.
Помимо указанных массивов будем использовать матрицу длин C , где элемент C – длина ребра (i,j) , если ребра нет, то ее длина полагается равной бесконечности, то есть больше любой фактической длины ребер. Фактически матрица C представляет собой матрицу смежности , в которой все нулевые элементы заменены на бесконечность.
Для определения самого
Для начала рассмотрим алгоритм Фалкерсона (графический способ упорядочивания элементов):
- 1. Найти вершины графа, в которые не входит не одна дуга. Они образуют первую группу. Пронумеровать вершины группы в произвольном порядке.
- 2. Вычеркнуть все пронумерованные вершины и дуги, из них исходящие. В получившемся графе найдется, по крайней мере, одна вершина, в которую не входит ни одна дуга. Этой вершине, входящей во вторую группу, присвоить очередной номер, и т. д. Второй шаг повторять до тех пор, пока не будут упорядочены все вершины.
Теперь рассмотрим алгоритм нахождения кратчайшего пути между двумя заданными вершинами в ориентированном графе. Пусть G = {S, U, ? } - ориентированный граф со взвешенными дугами. Обозначим s-вершину - начало пути и t-вершину - конец пути.
Алгоритм Дейкстры содержит одно ограничение - веса дуг должны быть положительными. Сам алгоритм состоит из двух этапов. На первом находится длина кратчайшего пути, на втором строится сам путь от вершины s к вершине t.
Этап 1. Нахождение кратчайшего пути.
Шаг 1. Присвоение вершинам начальных меток.
Полагаем d(s)=0* и считаем эту метку постоянной (постоянные метки помечаются сверху звёздочкой). Для остальных вершин x i S, x i ?s полагаем d(x i) = ? и считаем эти метки верными. Пусть x” = s, x” - обозначение текущей вершины.
Шаг 2. Изменение меток.
Для каждой вершины x i с временной меткой, непосредственно следующей за вершиной x”, меняем ее метку в соответствии со следующим правилом:
d нов. (x i) = min{d стар. (x i), d(x”)+щ(x”, x i)}.(1. 6. 1)
Шаг 3. Превращение метки из временной в постоянную.
Из всех вершин с временными метками выбираем вершину x j * с наименьшим значением метки
d(x j *) = min {d(x j) / x j S, d(x j) - временная}. (1. 6. 2)
Превращаем эту метку в постоянную и полагаем x” = x j *.
Шаг 4. Проверка на завершение первого этапа.
Если x” = t, то d(x”) - длина кратчайшего пути от s до t. В противном случае происходит возвращение ко второму шагу.
Этап 2. Построение кратчайшего пути.
Шаг 5. Последовательный поиск дуг кратчайшего пути.
Среди вершин, непосредственно предшествующих вершине x” c постоянными метками, находим вершину x i , удовлетворяющую соотношению
d(x”) = d(x i) + щ(x i , x”).(1. 6. 3)
Включаем дугу (x i , x”) в искомый путь и полагаем x” = x i .
Шаг 6. Проверка на завершение второго этапа.
Если x” = s, то кратчайший путь найден - его образует последовательность дуг, полученных на пятом шаге и выстроенных в обратном порядке. В противном случае возвращаемся к пятому шагу.
Пример 8: Задана весовая матрица? графа G. Найти минимальный путь из вершины x 1 в вершину x6 по алгоритму Дейкстры.
На рисунке 1. 11 изображён сам граф по данной матрице весов. Поскольку на данном графе есть цикл между вершинами x 2 , x 3 и x 5 , то вершины графа нельзя упорядочить по алгоритму Фалкерсона. На рисунке графа временные и постоянные метки указаны над соответствующей вершиной. Итак, распишем подробно работу алгоритма Дейкстры по шагам.
Шаг 1. Полагаем d(x 1) = 0*, x” = x 1 , d(x 2) = d(x 3) = d(x 4) = d(x 5) = d(x 6) = ?.
1-ая итерация.
Шаг 2. Множество вершин, непосредственно следующих за x” = x1 со временными метками S” = {x 2 , x 4 , x 5 }. Пересчитываем временные метки вершин: d(x 2) = min{?, 0*, + 9} = 9, d(x 4) = min{?, 0* + 6} = 6, d(x 5) = min{?, 0* + 11} = 11.
Шаг 3. Одна из временных меток превращается в постоянную min{9, ?, 6, 11, ?} = 6* = d(x 4), x” = x 4 .
Шаг 4. x” = x 4 ? t = x 6 , происходит возвращение на второй шаг.
2-ая итерация.
Шаг 2. S” = {x 2 , x 3 , x 5 }, d(x 2) = min{9, 6* + 5} = 9, d(x 3) = min {?, 6* + 7} = 13, d(x 5) = min{11, 6* + 6} = 11.
Шаг 3. min{d(x 2), d(x 3), d(x 5), d(x 6)} = min{9, 13, 11, ?} = 9* = d(x 2), x” = x 2 .
Шаг 4. x 2 ? x 6 , возвращение на второй шаг.
3-я итерация.
Шаг 2. S” ={x 3 }, d(x 3) = min{13, 9* + 8} = 13.
Шаг 3. min{d(x 3), d(x 5), d(x 6)} = min{31, 11, ?} = 11* = d(x 5), x” = x 5 .
Шаг 4. x 5 ? x 6 , возвращение на второй шаг.
4-ая итерация.
Шаг 2. S”={x 6 }, d(x 6) = min{?, 11* + 4} = 15.
Шаг 3. min {d(x 3), d(x 6)} = min{13, 15} = 13* = d(x 3), x” = x 3 .
Шаг 4. x 3 ? x 6 , возвращение на второй шаг.
5-ая итерация.
Шаг 2. S” = {x 6 }, d(x 6) = min{15, 13* + 9} = 15.
Шаг 3. min{d(x 6) } = min{15} = 15*, x” = x 6 .
Шаг 4. x 6 = t = x 6 , конец первого этапа.
Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x 6 с постоянными метками S” = {x 3 , x 5 }. Проверим для этих двух вершин выполнение равенства d нов. (x i) = min{d стар. (x i), d(x”) + щ(x”, x i)}:
d(x”) = 15 = 11* + 4 = d(x 5) + щ(x 5 , x 6),
d(x”) = 15 ? 13* + 9 = d(x 3) + щ(x 3 , x 6).
Включаем дугу (x 5 , x 6) в кратчайший путь. x” = x 5 .
Шаг 6. x” ? s = x 1 , возвращение на пятый шаг.
2-ая итерация.
Шаг 5. S” = {x 1 , x 4 }.
d(x”) = 11 = 0* + 11 = d(x 1) + щ(x 1 , x 5),
d(x”) = 11 ? 6* + 6 = d(x 4) + щ(x 4 , x 5).
Включаем дугу (x 1 , x 5) в кратчайший путь. x” = x 1 .
Шаг 6. x” = s = x 1 , завершение второго этапа.
Итак, кратчайший путь от вершины x 1 до вершины x 6 построен. Его длина (вес) равна 15, сам путь образует следующая последовательность дуг: м = (x 1 , x 5) - (x 5 , x 6).
Дан ориентированный или неориентированный взвешенный граф с вершинами и рёбрами. Веса всех рёбер неотрицательны. Указана некоторая стартовая вершина . Требуется найти длины кратчайших путей из вершины во все остальные вершины, а также предоставить способ вывода самих кратчайших путей.
Эта задача называется "задачей о кратчайших путях с единственным источником" (single-source shortest paths problem).
Алгоритм
Здесь описывается алгоритм, который предложил голландский исследователь Дейкстра (Dijkstra) в 1959 г.
Заведём массив , в котором для каждой вершины будем хранить текущую длину кратчайшего пути из в . Изначально , а для всех остальных вершин эта длина равна бесконечности (при реализации на компьютере обычно в качестве бесконечности выбирают просто достаточно большое число, заведомо большее возможной длины пути):
Кроме того, для каждой вершины будем хранить, помечена она ещё или нет, т.е. заведём булевский массив . Изначально все вершины не помечены, т.е.
Сам алгоритм Дейкстры состоит из итераций . На очередной итерации выбирается вершина с наименьшей величиной среди ещё не помеченных, т.е.:
(Понятно, что на первой итерации выбрана будет стартовая вершина .)
Выбранная таким образом вершина отмечается помеченной. Далее, на текущей итерации, из вершины производятся релаксации : просматриваются все рёбра , исходящие из вершины , и для каждой такой вершины алгоритм пытается улучшить значение . Пусть длина текущего ребра равна , тогда в виде кода релаксация выглядит как:
На этом текущая итерация заканчивается, алгоритм переходит к следующей итерации (снова выбирается вершина с наименьшей величиной , из неё производятся релаксации, и т.д.). При этом в конце концов, после итераций, все вершины графа станут помеченными, и алгоритм свою работу завершает. Утверждается, что найденные значения и есть искомые длины кратчайших путей из в .
Стоит заметить, что, если не все вершины графа достижимы из вершины , то значения для них так и останутся бесконечными. Понятно, что несколько последних итераций алгоритма будут как раз выбирать эти вершины, но никакой полезной работы производить эти итерации не будут (поскольку бесконечное расстояние не сможет прорелаксировать другие, даже тоже бесконечные расстояния). Поэтому алгоритм можно сразу останавливать, как только в качестве выбранной вершины берётся вершина с бесконечным расстоянием.
Восстановление путей . Разумеется, обычно нужно знать не только длины кратчайших путей, но и получить сами пути. Покажем, как сохранить информацию, достаточную для последующего восстановления кратчайшего пути из до любой вершины. Для этого достаточно так называемого массива предков : массива , в котором для каждой вершины хранится номер вершины , являющейся предпоследней в кратчайшем пути до вершины . Здесь используется тот факт, что если мы возьмём кратчайший путь до какой-то вершины , а затем удалим из этого пути последнюю вершину, то получится путь, оканчивающийся некоторой вершиной , и этот путь будет кратчайшим для вершины . Итак, если мы будем обладать этим массивом предков, то кратчайший путь можно будет восстановить по нему, просто каждый раз беря предка от текущей вершины, пока мы не придём в стартовую вершину — так мы получим искомый кратчайший путь, но записанный в обратном порядке. Итак, кратчайший путь до вершины равен:
Осталось понять, как строить этот массив предков. Однако это делается очень просто: при каждой успешной релаксации, т.е. когда из выбранной вершины происходит улучшение расстояния до некоторой вершины , мы записываем, что предком вершины является вершина :
Доказательство
Основное утверждение , на котором основана корректность алгоритма Дейкстры, следующее. Утверждается, что после того как какая-либо вершина становится помеченной, текущее расстояние до неё уже является кратчайшим, и, соответственно, больше меняться не будет.
Доказательство будем производить по индукции. Для первой итерации справедливость его очевидна — для вершины имеем , что и является длиной кратчайшего пути до неё. Пусть теперь это утверждение выполнено для всех предыдущих итераций, т.е. всех уже помеченных вершин; докажем, что оно не нарушается после выполнения текущей итерации. Пусть — вершина, выбранная на текущей итерации, т.е. вершина, которую алгоритм собирается пометить. Докажем, что действительно равно длине кратчайшего пути до неё (обозначим эту длину через ).
Рассмотрим кратчайший путь до вершины . Понятно, этот путь можно разбить на два пути: , состоящий только из помеченных вершин (как минимум стартовая вершина будет в этом пути), и остальная часть пути (она тоже может включать помеченные вершины, но начинается обязательно с непомеченной). Обозначим через первую вершину пути , а через — последнюю вершины пути .
Докажем сначала наше утверждение для вершины , т.е. докажем равенство . Однако это практически очевидно: ведь на одной из предыдущих итераций мы выбирали вершину и выполняли релаксацию из неё. Поскольку (в силу самого выбора вершины ) кратчайший путь до равен кратчайшему пути до плюс ребро , то при выполнении релаксации из величина действительно установится в требуемое значение.
Вследствие неотрицательности стоимостей рёбер длина кратчайшего пути (а она по только что доказанному равна ) не превосходит длины кратчайшего пути до вершины . Учитывая, что (ведь алгоритм Дейкстры не мог найти более короткого пути, чем это вообще возможно), в итоге получаем соотношения:
С другой стороны, поскольку и , и — вершины непомеченные, то так как на текущей итерации была выбрана именно вершина , а не вершина , то получаем другое неравенство:
Из этих двух неравенств заключаем равенство , а тогда из найденных до этого соотношений получаем и:
что и требовалось доказать.
Реализация
Итак, алгоритм Дейкстры представляет собой итераций, на каждой из которых выбирается непомеченная вершина с наименьшей величиной , эта вершина помечается, и затем просматриваются все рёбра, исходящие из данной вершины, и вдоль каждого ребра делается попытка улучшить значение на другом конце ребра.
Время работы алгоритма складывается из:
При простейшей реализации этих операций на поиск вершины будет затрачиваться операций, а на одну релаксацию — операций, и итоговая асимптотика алгоритма составляет:
Реализация :
const int INF = 1000000000 ; int main() { int n; ... чтение n ... vector < vector < pair< int ,int > > > g (n) ; ... чтение графа... int s = ...; // стартовая вершина vector< int > d (n, INF) , p (n) ; d[ s] = 0 ; vector< char > u (n) ; for (int i= 0 ; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }Здесь граф хранится в виде списков смежности: для каждой вершины список содержит список рёбер, исходящих из этой вершины, т.е. список пар >, где первый элемент пары — вершина, в которую ведёт ребро, а второй элемент — вес ребра.