Русская Википедия:Алгоритм Дейкстры
Алгори́тм Де́йкстры (Шаблон:Lang-en) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации OSPF и IS-IS.
Формулировка задачи
Примеры
Вариант 1. Дана сеть автомобильных дорог, соединяющих города Московской области. Некоторые дороги односторонние. Найти кратчайшие пути от города А до каждого города области (если двигаться можно только по дорогам).
Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.
Формальное определение
Дан взвешенный ориентированный[1] граф <math>G(V, E)</math> без дуг отрицательного веса[2]. Найти кратчайшие пути от некоторой вершины <math>a</math> графа <math>G</math> до всех остальных вершин этого графа.
Неформальное объяснение
Каждой вершине из 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-й вершиной ничего не делаем.
Следующий сосед — вершина 3, так как имеет минимальную метку.
Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а это меньше 17, поэтому метка не меняется.
Ещё один сосед вершины 2 — вершина 4.
Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22).
Поскольку 22<<math>\infty</math>, устанавливаем метку вершины 4 равной 22.
Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещённую.
Третий шаг.
Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:
Дальнейшие шаги.
Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.
Файл:Dijkstra graph12.PNG Файл:Dijkstra graph13.PNG Файл:Dijkstra graph14.PNG
Завершение выполнения алгоритма.
Алгоритм заканчивает работу, когда все вершины посещены.
Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.
Если в какой-то момент все непосещённые вершины помечены бесконечностью, то это значит, что до этих вершин нельзя добраться (то есть граф несвязный). Тогда алгоритм может быть завершён досрочно.
Алгоритм
Обозначения
- <math>V</math> — множество вершин графа
- <math>E</math> — множество рёбер графа
- <math>w[ij]</math> — вес (длина) ребра <math>ij</math>
- <math>a</math> — вершина, расстояния от которой ищутся
- <math>U</math> — множество посещённых вершин
- <math>d[u]</math> — по окончании работы алгоритма равно длине кратчайшего пути из <math>a</math> до вершины <math>u</math>
- <math>p[u]</math> — по окончании работы алгоритма содержит кратчайший путь из <math>a</math> в <math>u</math>
- <math>v</math> — текущая вершина, рассматриваемая алгоритмом
Код реализации алгоритма
Ниже приведён код реализации алгоритма на языке программирования Java. Данный вариант реализации не является лучшим, но наглядно показывает возможную реализацию алгоритма:
class Dijkstra {
double[] dist = new double[GV()];
Edge[] pred = new Edge[GV()];
public Dijkstra(WeightedDigraph G, int s) {
boolean[] marked = new boolean[GV()];
for (int v = 0; v <GV(); v++)
dist[v] = Double.POSITIVE_INFINITY;
MinPQplus<Double, Integer> pq;
pq = new MinPQplus<Double, Integer>(); \\Priority Queue
dist[s] = 0.0;
pq.put(dist[s], s);
while (!pq.isEmpty()) {
int v = pq.delMin();
if (marked[v]) continue;
marked(v) = true;
for (Edge e (v)) {
int w = e.to();
if (dist[w]> dist[v] + e.weight()) {
dist[w] = dist[v] + e.weight();
pred[w] = e;
pq.insert(dist[w], w);
}
}
}
}
}
Псевдокод
Присвоим <math>d[a] \gets 0,\ p[a] \gets 0</math>
Для всех <math>u \in V</math> отличных от <math>a</math> присвоим <math>d[u] \gets \infty</math>.
Пока <math>\exists v \notin U</math>. Пусть <math>v \notin U</math> — вершина с минимальным <math>d[v]</math> занесём <math>v</math> в <math>U</math>
Для всех <math>u \notin U</math> таких, что <math>vu \in E</math>
Если <math> d[u] > d[v] + w[vu]</math> то
Изменим <math>d[u] \gets d[v] + w [vu]</math>
Изменим <math>p[u] \gets (p[v], u)</math>
Описание
В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U — массив булевых переменных.
В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (бо́льшим максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.
На каждом шаге цикла мы ищем вершину <math>v</math> с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины <math>u</math>. Если в них (в <math>u</math>) расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 <math>d[i] = \infty</math>. Последний случай возможен тогда и только тогда, когда граф G несвязный.
Доказательство корректности
Пусть <math>l(v)</math> — длина кратчайшего пути из вершины <math>a</math> в вершину <math>v</math>. Докажем по индукции, что в момент посещения любой вершины <math>z</math> выполняется равенство <math>d(z)=l(z)</math>.
База. Первой посещается вершина <math>a</math>. В этот момент <math>d(a)=l(a)=0</math>.
Шаг. Пусть мы выбрали для посещения вершину <math>z\ne a</math>. Докажем, что в этот момент <math>d(z)=l(z)</math>. Для начала отметим, что для любой вершины <math>v</math> всегда выполняется <math>d(v)\ge l(v)</math> (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть <math>P</math> — кратчайший путь из <math>a</math> в <math>z</math>. Вершина <math>z</math> находится на <math>P</math> и не посещена. Поэтому множество непосещённых вершин на <math>P</math> непусто. Пусть <math>y</math> — первая непосещённая вершина на <math>P</math>, <math>x</math> — предшествующая ей (следовательно, посещённая). Поскольку путь <math>P</math> кратчайший, его часть, ведущая из <math>a</math> через <math>x</math> в <math>y</math>, тоже кратчайшая, следовательно <math>l(y)=l(x)+w(xy)</math>.
По предположению индукции, в момент посещения вершины <math>x</math> выполнялось <math>d(x)=l(x)</math>, следовательно, вершина <math>y</math> тогда получила метку не больше чем <math>d(x)+w(xy)=l(x)+w(xy)=l(y)</math>. Следовательно, <math>d(y)=l(y)</math>. Если <math>z=y</math>, то индукционный переход доказан. Иначе, поскольку сейчас выбрана вершина <math>z</math>, а не <math>y</math>, метка <math>z</math> минимальна среди непосещённых, то есть <math>d(z)\le d(y)=l(y)\le l(z)</math>. Комбинируя это с <math>d(z)\ge l(z)</math>, имеем <math>d(z)=l(z)</math>, что и требовалось доказать.
Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент <math>d=l</math> для всех вершин.
Сложность алгоритма
Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещённых вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество рёбер в графе G.
- В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается всё множество вершин, а для хранения величин d используется массив, время работы алгоритма есть <math>O(n^2)</math>. Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма <math>O(n^2+m)</math>, но, так как <math>m \le n(n-1)</math>, оно составляет <math>O(n^2)</math>.
- Для разреженных графов (то есть таких, для которых m много меньше n²) непосещённые вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время удаления вершины из <math>\overline U</math> станет <math>\log n</math> при том, что время модификации <math>d[i]</math> возрастёт до <math>\log n</math>. Так как цикл выполняется порядка n раз, а количество смен меток не больше m, время работы такой реализации — <math>O(n \log n + m \log n)</math>.
- Если для хранения непосещённых вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за <math>O(\log n)</math>, а уменьшение значения в среднем за <math>O(1)</math>, то время работы алгоритма составит <math>O(n \log n + m)</math>. Однако согласно лекциям Алексеева и Таланова[3]:
Шаблон:Начало цитаты скрытые константы в асимптотических оценках трудоёмкости велики и использование фибоначчиевых куч редко оказывается целесообразным: обычные двоичные (Шаблон:Нп1) кучи на практике эффективнее. Шаблон:Конец цитаты
Альтернативами им служат толстые кучи, тонкие кучи и Шаблон:Нп1, обладающие теми же асимптотическими оценками, но меньшими константами[4].
См. также
- Очередь с приоритетом (программирование)
- Минимальное остовное дерево
- Остовное дерево
- Задача о кратчайшем пути
- Алгоритм Борувки
- Алгоритм Краскала
- Алгоритм обратного удаления
- Алгоритм Прима
Примечания
Литература
Ссылки
- C. Анисимов. Как построить кратчайший маршрут между двумя точками.
- Реализация простейшего варианта алгоритма Дейкстры на e-maxx.ru
- Реализация варианта алгоритма Дейкстры для разреженных графов на e-maxx.ru
- Реализация варианта алгоритма Дейкстры с корневой эвристикой
- Алгоритм Дейкстры. Код программы на Python
- Пример на YouTube
- Dijkstra’s algorithm — реализация алгоритма на разных языках на Шаблон:Iw.
Шаблон:Алгоритмы поиска на графах
- ↑ Частными случаями ориентированного графа являются неориентированный и смешанный («частично ориентированный») графы.
- ↑ Для графа с отрицательными весами применяется более общий алгоритм — Алгоритм Дейкстры с потенциалами
- ↑ Владимир Алексеев, Владимир Таланов, Курс «Структуры данных и модели вычислений», Лекция № 7: Биномиальные и фибоначчиевы кучи // 26.09.2006, Интуит.ру
- ↑ Владимир Алексеев, Владимир Таланов, Курс «Структуры данных и модели вычислений», Лекция № 8: Тонкие кучи // 26.09.2006, Интуит.ру
