Вычислительная сложность алгоритма дейкстры. Нахождение кратчайших путей. Алгоритм Дейкстры. Новая постановка задачи с собеседования
Дан ориентированный или неориентированный взвешенный граф с вершинами и рёбрами. Веса всех рёбер неотрицательны. Указана некоторая стартовая вершина . Требуется найти длины кратчайших путей из вершины во все остальные вершины, а также предоставить способ вывода самих кратчайших путей.
Эта задача называется "задачей о кратчайших путях с единственным источником" (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; } } } }Здесь граф хранится в виде списков смежности: для каждой вершины список содержит список рёбер, исходящих из этой вершины, т.е. список пар >, где первый элемент пары — вершина, в которую ведёт ребро, а второй элемент — вес ребра.
Решить задачу о нахождении кратчайшего пути алгоритмом Дейкстры.
Найти кратчайший путь от Х0 до Х7. Граф задан элементами стоимостной матрицы
Построим этот граф
Начнем с элемента Х0 и присвоим ему метку 0, рассмотрим всех его соседей, т.к. там еще нет пометок, то присвоим им соответствующие длины:
Все соседи Х0 рассмотрены, помечаем ее и переходим к вершине Х1. ЕЕ соседи Х0, Х2,Х4, но Х0 помечена, не рассматриваем ее. Для Х2: 
, оставляем метку.
Для Х4: 
, заменяем метку. Все соседи вершины Х1 рассмотрены, помечаем ее
переходим к вершине Х2. ЕЕ соседи Х0, Х1,Х3, Х4, Х5, Х6, но Х0, Х1 помечены, не рассматриваем их.
Для Х3: 
, оставляем метку.
Для Х5: 
, заменяем метку.
Для Х4: 
, оставляем метку.
Для Х6: 
, заменяем метку.
Все соседи вершины Х2 рассмотрены, помечаем ее.
переходим к вершине Х3. ЕЕ соседи Х0, Х2, Х6, но Х0, Х2 помечены, не рассматриваем их.
Для Х6: 
, оставляем метку.
Все соседи вершины Х3 рассмотрены, помечаем ее.
переходим к вершине Х4. ЕЕ соседи Х1,Х2, Х5, Х7, но Х1, Х2 помечены, не рассматриваем их.
Для Х5: 
, заменяем метку.
Для Х7: 
, заменяем метку.
Все соседи вершины Х4 рассмотрены, помечаем ее.
переходим к вершине Х5. ЕЕ соседи Х2,Х4, Х6, Х7, но Х2, Х4 помечены, не рассматриваем их.
Для Х6: 
, оставляем метку.
Для Х7: 
, оставляем метку.
Все соседи вершины Х5 рассмотрены, помечаем ее.
переходим к вершине Х6. ЕЕ соседи Х2,Х3, Х5, Х7, но Х2, Х3, Х5 помечены, не рассматриваем их.
Для Х7: 
, оставляем метку.
Все соседи вершины Х6 рассмотрены, помечаем ее. И помечаем оставшуюся Х7, все вершины рассмотрены.
Вывод: Кратчайший путь их Х0 в Х7 имеет длину 101, этот путь: Х7-Х4-Х1-Х0.
Для начала рассмотрим алгоритм Фалкерсона (графический способ упорядочивания элементов):
- 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).
Постановка задачи очень похожа на задачу, решаемую алгоритмом Форда-Беллмана: требуется найти кратчайший путь от выделенной вершины взвешенного графа (начальной) до всех остальных. Единственное отличие - теперь веса всех ребер неотрицательны.Описание алгоритма
Разобьем все вершины на два множества: уже обработанные и еще нет. Изначально все вершины необработанные, и расстояния до всех вершин, кроме начальной, равны бесконечности, расстояние до начальной вершины равно 0.На каждой итерации из множества необработанных вершин берется вершина с минимальным расстоянием и обрабатывается: происходит релаксация всех ребер, из нее исходящих, после чего вершина помещается во множество уже обработанных вершин.
Напоминаю, что релаксация ребра (u, v), как и в алгоритме Форда-Беллмана, заключается в присваивании dist[v] = min(dist[v], dist[u] + w), где dist[v] - расстояние от начальной вершины до вершины v, а w - вес ребра из u в v.
Реализация
В самой простой реализации алгоритма Дейкстры нужно в начале каждой итерации пройтись по всем вершинам для того, чтобы выбрать вершину с минимальным расстоянием. Это достаточно долго, хотя и бывает оправдано в плотных графах, поэтому обычно для хранения расстояний до вершин используется какая-либо структура данных. Я буду использовать std::set, просто потому, что не знаю, как изменить элемент в std::priority_queue =)Также я предполагаю, что граф представлен в виде vector
Dijkstra
Доказательство корректности
Предположим, алгоритм был запущен на некотором графе из вершины u и выдал неверное значение расстояния для некоторых вершин, причем v - первая из таких вершин (первая в смысле порядка, в котором алгоритм выплевывал вершины). Пусть w - ее предок в кратчайшем пути из u в v.Заметим, что расстояние до w подсчитано верно по предположению
- Пусть найденное алгоритмом dist"[w] < dist[v]. Тогда рассмотрим последнюю релаксацию ребра, ведущего в v: (s, v). Расстояние до s было подсчитано верно, значит, существует путь из u в v веса dist[s] + w = dist"[v] < dist[v]. Противоречие
- Пусть найденное алгоритмом dist"[w] > dist[v]. Тогда рассмотрим момент обработки вершины w. В этот момент было релаксировано ребро (w, v), и, соответственно, текущая оценка расстояния до вершины v стала равной dist[v], а в ходе следующих релаксаций она не могла уменьшиться. Противоречие
Заметим, что если в графе были ребра отрицательного веса, то вершина w могла быть выплюнута позже, чем вершина v, соответственно, релаксация ребра (w, v) не производилась. Алгоритм Дейкстры работает только для графов без ребер отрицательного веса!
Сложность алгоритма
Вершины хранятся в некоторой структуре данных, поддерживающей операции изменения произвольного элемента и извлечения минимального.Каждая вершина извлекается ровно один раз, то есть, требуется O(V) извлечений.
В худшем случае, каждое ребро приводит к изменению одного элемента структуры, то есть, O(E) изменений.
Если вершины хранятся в простом массиве и для поиска минимума используется алгоритм линейного поиска, временная сложность алгоритма Дейкстры составляет O(V * V + E) = O(V²).
Если же используется очередь с приоритетами, реализованная на основе двоичной кучи (или на основе set), то мы получаем O(V log V + E log E) = O(E log V).
Если же очередь с приоритетами была реализована на основе кучи Фибоначчи, получается наилучшая оценка сложности O(V log V + E).
Но при чем же здесь задача с собеседования в Twitter?
Задачу с самого собеседования решать не очень интересно, поэтому я предлагаю ее усложнить. Перед дальнейшим чтением статьи я рекомендую ознакомиться с оригинальной постановкой задачиНовая постановка задачи с собеседования
- Назовем задачу с собеседования «одномерной». Тогда в k-мерном аналоге будут столбики, пронумерованные k числами, для каждого из которых известна высота. Вода может стекать со столбика в соседний столбик меньшей высоты, либо за край.
- Что такое «соседние столбики»? Пусть у каждого столбика есть свой список соседей, какой угодно. Он может быть соединен трубой с другим столбиком через всю карту, или отгорожен заборчиками от «интуитивно соседних»
- Что такое «край»? Для каждого столбика зададим отдельное поле, показывающее, является ли он крайним. Может, у нас дырка в середине поля?
Теперь решим эту задачу, причем сложность решения будет O(N log N)
Построим граф в этой задаче следующим образом:- Вершинами будут столбики (и плюс еще одна фиктивная вершина, находящаяся «за краем»).
- Две вершины будут соединены ребром, если в нашей системе они соседние (или если одна из этих вершин - «край», в другая - крайний столбик)
- Вес ребра будет равен максимуму из высот двух столбиков, которые он соединяет
Теперь все встает на свои места: для того, чтобы попасть за край из некоторого центрального столбика, нужно пройти по некоторому пути (по которому вода и будет стекать), причем максимальная из высот столбиков этого пути в лучшем случае как раз совпадет с «расстоянием» от начального столбика до «края» (или, поскольку граф не является ориентированным, от «края» до начального столбика). Осталось лишь применить алгоритм Дейкстры.
Реализация
void Dijkstra(int v)
{
// Инициализация
int n = (int)edges.size();
dist.assign(n, INF);
dist[v] = 0;
set
Но это же сложнее и дольше, чем оригинальное решение! Кому это вообще нужно?!
Обращаю Ваше внимание, что мы решали задачу в общем виде. Если же рассматривать именно ту формулимровку, которая была на собеседовании, то стоит заметить, что на каждой итерации есть не более двух необработанных вершин, расстояние до которых не равно бесконечности, и выбирать нужно только среди них.Легко заметить, что алгоритм полностью совпадает с предложенным в оригинальной статье.
Была ли эта задача хорошей?
Я думаю, эта задача хорошо подходит для объяснения алгоритма Дейкстры. Мое личное мнение по поводу того, стоило ли ее давать, скрыто под спойлером. Если Вы не хотите его видеть - не открывайте.Скрытый текст
Если человек хоть немного разбирается в графах, он точно знает алгоритм Дейкстры - он один из самых первых и простых. Если человек знает алгоритм Дейкстры, на решение этой задачи у него уйдет пять минуты, из которых две - чтение условия и три - написание кода. Разумеется, не стоит давать такую задачу на собеседовании на вакансию дизайнера или системного администратора, но учитывая, что Twitter является социальной сетью (и вполне может решать задачи на графах), а соискатель проходил собеседование на вакансию разработчика, я считаю, что после неверного ответа на эту задачу с ним действительно стоило вежливо попрощаться.
Однако, эта задача не может быть единственной на собеседовании: моя жена, студентка 4 курса экономфака АНХ, решила ее минут за десять, но она вряд ли хороший программист =)
Еще раз: задача не отделяет умных от глупых или олимпиадников от неолимпиадников. Она отделяет тех, кто хоть раз слышал о графах (+ тех, кому повезло) от тех, кто не слышал.
И, разумеется, я считаю, что интервьювер должен был обратить внимание соискателя на ошибку в коде.
PS
В последнее время я писал небольшой цикл статей об алгоритмах. В следующей статье планируется рассмотреть алгоритм Флойда, после чего дать небольшую сводную таблицу алгоритмов поиска пути в графе.Алгори́тм Де́йкстры (Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием Сначала Кратчайший Путь (Shortest Path First ).
Примеры
Вариант 1. Дана сеть автомобильных дорог, соединяющих города Новосибирской области. Некоторые дороги односторонние. Найти кратчайшие пути от Новосибирска до каждого города области (если двигаться можно только по дорогам).
Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.
Формальное определение
Дан взвешенный ориентированный граф G (V , E ) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.
Неформальное объяснение
Каждой вершине из V сопоставим метку - минимальное известное расстояние от этой вершины до a . Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация . Метка самой вершины a полагается равной 0, метки остальных вершин - бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Шаг алгоритма . Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u , имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u , назовем соседями этой вершины. Для каждого соседа вершины u , кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 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-й вершиной ничего не делаем.
Следующий сосед вершины 2 - вершина 3, так имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.
Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояние до 2-ой вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22<, устанавливаем метку вершины 4 равной 22.
Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.
Третий шаг . Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:
Дальнейшие шаги . Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.
Завершение выполнения алгоритма . Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.
Алгоритм
Обозначения
V - множество вершин графа
E - множество ребер графа
w [ij ] - вес (длина) ребраij
a - вершина, расстояния от которой ищутся
U - множество посещенных вершин
d [u ] - по окончании работы алгоритма равно длине кратчайшего пути изa до вершиныu
p [u ] - по окончании работы алгоритма содержит кратчайший путь изa вu
Псевдокод
Присвоим
Для всех отличных от a
присвоим
Пусть - вершина с минимальнымd [v ]
Для всех таких, что
еслиd [u ] >d [v ] +w [vu ]то
Описание
В простейшей реализации для хранения чисел d [i ] можно использовать массив чисел, а для хранения принадлежности элемента множеству U - массив булевых переменных.
В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (бо́льшим максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.
На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 . Последний случай возможен тогда и только тогда, когда граф G не связан.
Доказательство правильности
Пусть l(v) - длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z). База. Первой посещается вершина a. В этот момент d(a)=l(a)=0. Шаг. Пускай мы выбрали для посещения вершину . Докажем, что в этот момент d(z)=l(z). Для начала отметим, что для любой вершины v, всегда выполняется (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P - кратчайший путь из a в z, y - первая непосещённая вершина на P, x - предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть, ведущая из a через x в y, тоже кратчайшая, следовательно l(y)=l(x)+w(xy). По предположению индукции, в момент посещения вершины x выполнялось d(x)=l(x), следовательно, вершина y тогда получила метку не больше чем d(x)+w(xy)=l(x)+w(xy)=l(y). Следовательно, d(y)=l(y). С другой стороны, поскольку сейчас мы выбрали вершину z, её метка минимальна среди непосещённых, то есть . Комбинируя это с , имеем d(z)=l(z), что и требовалось доказать.
Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент d=l для всех вершин.
