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

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

Содержание

Формулировка задачи

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

Вариант 2. Дана карта велодорожек Латвии и Белоруссии. Найти минимальное расстояние, которое надо проехать, чтобы добраться от Риги до Бобруйска.

Вариант 3. Есть план города с нанесёнными на него местами расположения пожарных частей. Определить ближайшую к каждому дому пожарную станцию.

Абстракция

Дан неориентированный связанный граф G(V, U). Найти расстояние от вершины a до всех остальных вершин V.

Интуитивное объяснение

Будем хранить текущее минимальное расстояние до всех вершин V (от данной вершины a) и на каждом шаге алгоритма пытаться уменьшить это расстояние. Первоначально установим расстояния до всех вершин равным бесконечности, а до вершины а — нулю. Рассмотрим выполнение алгоритма на примере. Пусть нужно найти расстояния от 1-й вершины до всех остальных. Кружочками обозначены вершины, линиями — пути между ними («дуги»). Над дугами обозначена их «цена» — длина пути. Красным обозначено текущее кратчайшее расстояние до вершины.

Шаг 1

Инициализация. Расстояния до всех вершин графа V = \infty. Расстояние до а = 0. Ни одна вершина графа не обработана.

Шаг 2

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

Шаг 3

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

Шаги 4, 5

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

Шаг 6

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

Шаг 7

Практически происходит возврат к шагу 2. Снова находим «ближайшую» необработанную (невычеркнутую) вершину. Это вершина 2 с текущим кратчайшим расстоянием до неё = 7. И снова пытаемся уменьшить расстояние до всех соседей 2-й вершины, пытаясь пройти в них через 2-ю. Соседями 2-й вершины являются 1, 3, 4.

Шаг 8

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

Шаг 8

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

Шаг 9

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

Шаг 10

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

Шаги 11 — 15

По уже «отработанной» схеме повторяем шаги 2 — 6. Теперь самой «близкой» оказывается вершина № 3. После ее «обработки» получим такие результаты:

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

Проделываем то же самое с оставшимися вершинами (№ по порядку: 6, 4 и 5).

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

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

Простейшая реализация

Простейшая реализация алгоритма Дейкстры требует O(V2) действий. В ней используется массив для расстояний и массив флагов.

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

На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1.

В математических терминах

Пусть u — вершина, расстояния от которой ищутся, V — множество вершин графа, di — расстояние от вершины u до вершины i, w(i, j) — вес ребра (i, j).


Алгоритм:

1. Множество вершин U, до которых расстояние известно, устанавливается равным {u}.

2. Если U=V, алгоритм завершен.

3. Потенциальные расстояния Di до вершин из U\V устанавливаются в бесконечность.

4. Для всех рёбер (i, j), где i∈U и j∈V\U, если Dj>di+w(i, j), то Dj присваивается di+w(i, j).

5. Ищется i∈V\U, при котором Di минимально.

6. Если Di = \infty, алгоритм закончен. Иначе di присваивается значение Di, U присваивается U∪{i} и осуществляется переход на шаг 2.


См. также

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home