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

Материал из Википедии — свободной энциклопедии

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

[править] Формулировка задачи

Вариант 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-й вершиной ничего не делаем.

[править] Шаг 9

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

[править] Шаг 10

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

[править] Шаг 11

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

[править] Шаги 12 — 16

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

[править] Дальнейшие шаги

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

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

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

[править] Пример реализации

[править] Обозначения

s — вершина, расстояния от которой ищутся,
V — множество вершин графа,
d[i] — набор вещественных чисел в которых по окончанию работы алгоритма будет храниться расстояние от вершины s до вершины i.
ω[ij] - вес ребра ij.

[править] Алгоритм

Присвоим $d[s] \gets 0$

Для всех $u \in V$ отличных от $s$

$d[u] \gets +\infty$

Пока $\exists u \in \overline U$ и $d[u] < +\infty$

Пусть v - вершина из $\overline U$ с минимальным

d [v]

Добавим к

U

вершину

v

Для всех $u \in \overline U$ таким что $vu \in E$

если

d [u] > d [v] + ω[v u]

изменим $d[u] \gets d[v] + \omega [vu]$

[править] Описание

В простейшей реализации для хранения чисел $d [i]$ можно использовать массив чисел, а для хранения принадлежности элемента множеству $\overline U$ - массив булевский переменных.

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

На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1, либо когда у всех вершин у которых флаг равен 0 $d[i] = +\infty$ . Последний случай возможен когда граф несвязанный.

[править] Дополнительная информация

При реализации алгоритма можно пользоваться разными способами нахождения вершины $v$ , а также можно по разному модифицировать вес вершин. В зависимости от этого скорость работы алгоритма будет меняться.

В простейшем случае если для поиска вершины с минимальным $d [v]$ мы будем просматривать все множество вершин, а для хранения величин d - массив, мы получим скорость работы $O (n 2 + m)$ . Основной цикл выполняется порядка n раз, а на нахождение минимума мы тратим порядка n операций, плюс количество релаксаций, которое не больше чем количество ребер в исходном графе.
Если же вершины из $\overline U$ держать в двоичной куче, а в качестве ключа использовать значения $d [i]$ , то скорость несмотря на то, что скорость извлечения вершины их $\overline U$ станет $log n$ , время модификации $d [i]$ возрастет до $log n$ . Т.к. цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации $O (n log n + m log n)$
Если для хранения $\overline U$ использовать фибоначчиевы кучи у которых время добавления элемента $O (1)$ , то время работы алгоритма составит $O (n log n + m)$

[править] Замечание

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

[править] См. также

Алгоритм Дейкстры с потенциалами — обобщение на случай графов с рёбрами отрицательного веса
Shortest Path First
OSPF

[править] Links

algolist.manual.ru

Категория: Алгоритмы на графах