Алгоритм дейкстры поиска дерева кратчайших путей. Алгоритм дейкстры

Dijkstra

> q; for (int i = 0; i < n; ++i) { q.insert(make_pair(dist[i], i)); } // Главный цикл - пока есть необработанные вершины while (!q.empty()) { // Достаем вершину с минимальным расстоянием pair < (int)edges.size(); ++i) { // Делаем релаксацию if (dist[i].first] > cur.first + edges[i].second) { q.erase(make_pair(dist[i].first], edges[i].first)); dist[i].first] = cur.first + edges[i].second; q.insert(make_pair(dist[i].first], edges[i].first)); } } } }

Доказательство корректности

• Пусть найденное алгоритмом 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], а в ходе следующих релаксаций она не могла уменьшиться. Противоречие

Сложность алгоритма

Но при чем же здесь задача с собеседования в Twitter?

Новая постановка задачи с собеседования

• Назовем задачу с собеседования «одномерной». Тогда в k-мерном аналоге будут столбики, пронумерованные k числами, для каждого из которых известна высота. Вода может стекать со столбика в соседний столбик меньшей высоты, либо за край.
• Что такое «соседние столбики»? Пусть у каждого столбика есть свой список соседей, какой угодно. Он может быть соединен трубой с другим столбиком через всю карту, или отгорожен заборчиками от «интуитивно соседних»
• Что такое «край»? Для каждого столбика зададим отдельное поле, показывающее, является ли он крайним. Может, у нас дырка в середине поля?

Теперь решим эту задачу, причем сложность решения будет O(N log N)

• Вершинами будут столбики (и плюс еще одна фиктивная вершина, находящаяся «за краем»).
• Две вершины будут соединены ребром, если в нашей системе они соседние (или если одна из этих вершин - «край», в другая - крайний столбик)
• Вес ребра будет равен максимуму из высот двух столбиков, которые он соединяет

Реализация

void Dijkstra(int v) { // Инициализация int n = (int)edges.size(); dist.assign(n, INF); dist[v] = 0; set > q; for (int i = 0; i > n; ++i) { q.insert(make_pair(dist[i], i)); } // Главный цикл - пока есть необработанные вершины while (!q.empty()) { // Достаем вершину с минимальным расстоянием pair cur = *q.begin(); q.erase(q.begin()); // Проверяем всех ее соседей for (int i = 0; i < (int)edges.size(); ++i) { // Делаем релаксацию if (dist[i].first] > max(cur.first, edges[i].second)) { q.erase(make_pair(dist[i].first], edges[i].first)); dist[i].first] = max(cur.first, edges[i].second); q.insert(make_pair(dist[i].first], edges[i].first)); } } } }

Но это же сложнее и дольше, чем оригинальное решение! Кому это вообще нужно?!

Была ли эта задача хорошей?

Скрытый текст

Если человек хоть немного разбирается в графах, он точно знает алгоритм Дейкстры - он один из самых первых и простых. Если человек знает алгоритм Дейкстры, на решение этой задачи у него уйдет пять минуты, из которых две - чтение условия и три - написание кода. Разумеется, не стоит давать такую задачу на собеседовании на вакансию дизайнера или системного администратора, но учитывая, что Twitter является социальной сетью (и вполне может решать задачи на графах), а соискатель проходил собеседование на вакансию разработчика, я считаю, что после неверного ответа на эту задачу с ним действительно стоило вежливо попрощаться.
Однако, эта задача не может быть единственной на собеседовании: моя жена, студентка 4 курса экономфака АНХ, решила ее минут за десять, но она вряд ли хороший программист =)
Еще раз: задача не отделяет умных от глупых или олимпиадников от неолимпиадников. Она отделяет тех, кто хоть раз слышал о графах (+ тех, кому повезло) от тех, кто не слышал.
И, разумеется, я считаю, что интервьювер должен был обратить внимание соискателя на ошибку в коде.

PS

Алгоритм Дейкстры предназначен для нахождения кратчайшего пути между вершинами в неориентированном графе.

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

Пример 1. Найти кратчайший путь на графе от вершины L до вершины D (рис. 10.7).

Рис. 10.7.

Запишем алгоритм в виде последовательности шагов (табл. 10.1). Шаг 1. Определяем расстояния от начальной вершины L до всех остальных.

Таблица 10.1

Метод Дейкстры (первый шаг)

Шаг 2. Выбираем наименьшее расстояние от L до В; найденная вершина В принимается за вновь выбранную. Найденное наименьшее расстояние добавляем к длинам ребер от новой вершины В до всех остальных. Выбираем минимальное расстояние от В до N. Новую вершину N принимаем за выбранную (табл. 10.2).

Таблица 10.2

Метод Дейкстры (второй шаг)

Для наглядности в дальнейшем вместо знака оо будем ставить знак « - ».

Шаг 3. Определяем расстояния от вершины N л о всех оставшихся (за исключением L и В), как показано в табл. 10.3.

Таблица 10.3

Метод Дейкстры (третий шаг)

Расстояние от вершины L через вершину N до вершины G равно 18 условных единиц. Это расстояние больше, чем расстояние LB + BG = 16 условных единиц, вследствие чего оно не учитывается в дальнейшем. Продолжая аналогичные построения, составим табл. 10.4. Таким образом, найдена длина кратчайшего пути между вершинами L и D (44 условных единицы).

Траекторию пути определяем следующим образом. Выполняем обратный просмотр от конечной вершины к начальной. Просматриваем столбец, соответствующий вершине, снизу вверх и фиксируем первое появление минимальной величины. В столбце, соответствующем вершине D, впервые минимальная длина 44 условных единицы появилась снизу в четвертой строке. В этой строке указана вершина S, к которой следует перейти, т.е. следующим нужно рассматривать столбец, соответствующий вершине S.

Таблица 10.4

В этом столбце минимальная длина, равная 27 условным единицам, указывает следующую вершину G, к которой надлежит перейти, и т.д. Таким образом, получаем траекторию пути: (L, В, G, S, D).

Пример 8. Найти кратчайший путь на графе между 1-й и 7-й вершинами (рис. 10.8).

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

Рис. 10.8. Граф (а) и соответствующая ему матрица смежности (б)

Табличная реализация метода Дейкстры

Таблица 10.5

Выполняем обратный просмотр от конечной вершины к начальной.

Просматриваем столбец, соответствующий вершине, снизу вверх и фиксируем первое появление минимальной величины. Кратчайший путь при этом будет равен (V 7 - V 5 - V 2 - У {).

и КОНТРОЛЬНЫЕ ВОПРОСЫ

• 1. Какова теоретическая сложность алгоритмов: построения дерева решений, динамического программирования и Дейкстры?
• 2. В чем особенность использования дерева решений для ориентированного и неорентированного графа?
• 3. В решении каких прикладных задач используются алгоритмы определения в графе кратчайших расстояний между заданными вершинами?
• 4. Может ли быть применен рассмотренный в работе алгоритм Дейкстры к определению кратчайшего расстояния в ориентированном графе?
• 5. Как работает алгоритм Дейкстры?
• 6. Как работает алгоритм динамического программирования применительно к задаче определения в графе кратчайших расстояний между вершинами?

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

Рассмотрим три наиболее эффективных алгоритма нахождения кратчайшего пути :

• алгоритм Дейкстры ;
• алгоритм Флойда ;
• переборные алгоритмы.

Указанные алгоритмы легко выполняются при малом количестве вершин в графе. При увеличении их количества задача поиска кратчайшего пути усложняется.

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

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

Каждой вершине приписывается вес – это вес пути от начальной вершины до данной. Также каждая вершина может быть выделена. Если вершина выделена, то путь от нее до начальной вершины кратчайший, если нет – то временный. Обходя граф , алгоритм считает для каждой вершины маршрут , и, если он оказывается кратчайшим, выделяет вершину. Весом данной вершины становится вес пути. Для всех соседей данной вершины алгоритм также рассчитывает вес , при этом ни при каких условиях не выделяя их. Алгоритм заканчивает свою работу, дойдя до конечной вершины, и весом кратчайшего пути становится вес конечной вершины.

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

Шаг 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине – 0.

Шаг 2. Все вершины не выделены.

Шаг 3. Первая вершина объявляется текущей.

Шаг 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра , соединяющего текущую вершину с невыделенной.

Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход . Иначе, текущей становится найденная вершина . Она же выделяется.

Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.

Шаг 7. Переход на шаг 4.

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

Помимо указанных массивов будем использовать матрицу длин C , где элемент C – длина ребра (i,j) , если ребра нет, то ее длина полагается равной бесконечности, то есть больше любой фактической длины ребер. Фактически матрица C представляет собой матрицу смежности , в которой все нулевые элементы заменены на бесконечность.

Для определения самого

По завершению турнира «Новогодняя ночь» спонсор решил отправить $m$ призерам подарки по почте. Зная количество участников $n$ и время доставки почты между некоторыми отделениями «Укрпочты», найти, через какое минимальное время последний из призеров получит свой приз.

Входные данные

Первая строка содержит $3$ числа: количество участников турнира $n$, количество призов спонсора $m$ и количество известных временных сроков доставки между некоторыми из отделений $k$. В следующей строке через пробел указаны номера участников, ставших призёрами.

Далее идет $k$ строк по $3$ числа в каждой с информацией об известных сроках доставки между некоторыми из отделений в формате: $a$ $b$ $t$, где $a$ и $b$ — номера отделений, $t$ $(0 \leqslant t \leqslant 365)$ — время доставки почты между ними. В последней строке находится единственное число — номер почтового отделения, из которого спонсор будет отправлять призы. Известно, что $1 \leqslant n, m, a, b \leqslant 365$.

Выходные данные

Если все призы будут доставлены участникам — вывести в первой строке «The good sponsor!», а в следующей — время, через какое последний из призеров получит свой приз. Если хотя бы один из участников не сможет получить приз — вывести в единственной строке «It is not fault of sponsor…». Фразы выводить без кавычек.

Тесты

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

Эта задача называется "задачей о кратчайших путях с единственным источником" (single-source shortest paths problem).

Алгоритм

Здесь описывается алгоритм, который предложил голландский исследователь Дейкстра (Dijkstra) в 1959 г.

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

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

Сам алгоритм Дейкстры состоит из итераций . На очередной итерации выбирается вершина с наименьшей величиной среди ещё не помеченных, т.е.:

(Понятно, что на первой итерации выбрана будет стартовая вершина .)

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

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

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

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

Осталось понять, как строить этот массив предков. Однако это делается очень просто: при каждой успешной релаксации, т.е. когда из выбранной вершины происходит улучшение расстояния до некоторой вершины , мы записываем, что предком вершины является вершина :

Доказательство

Основное утверждение , на котором основана корректность алгоритма Дейкстры, следующее. Утверждается, что после того как какая-либо вершина становится помеченной, текущее расстояние до неё уже является кратчайшим, и, соответственно, больше меняться не будет.

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

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

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

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

С другой стороны, поскольку и , и — вершины непомеченные, то так как на текущей итерации была выбрана именно вершина , а не вершина , то получаем другое неравенство:

Из этих двух неравенств заключаем равенство , а тогда из найденных до этого соотношений получаем и:

что и требовалось доказать.

Реализация

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

Время работы алгоритма складывается из:

При простейшей реализации этих операций на поиск вершины будет затрачиваться операций, а на одну релаксацию — операций, и итоговая асимптотика алгоритма составляет:

Реализация :

Здесь граф хранится в виде списков смежности: для каждой вершины список содержит список рёбер, исходящих из этой вершины, т.е. список пар >, где первый элемент пары — вершина, в которую ведёт ребро, а второй элемент — вес ребра.