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

Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации OSPF и IS-IS.

Блок-схема алгоритма Дейкстры.

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

ПримерыПравить

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

Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

Формальное определениеПравить

Дан взвешенный ориентированный граф $G(V,E)$$G(V,E)$  без дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины $a$$a$  графа $G$$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-й вершиной ничего не делаем.

Следующий сосед — вершина 3, так как имеет минимальную метку.

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

 

Ещё один сосед вершины 2 — вершина 4.

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

Поскольку 22<$\mathrm{\infty <!--\; \infty \; -->}$$\infty$ , устанавливаем метку вершины 4 равной 22.

 

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

 

Третий шаг.

Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

 

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

Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

     

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

Алгоритм заканчивает работу, когда все вершины посещены.

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

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

АлгоритмПравить

ОбозначенияПравить

• $V$$V$  — множество вершин графа
• $E$$E$  — множество рёбер графа
• $w[ij]$$w[ij]$  — вес (длина) ребра $ij$$ij$ 
• $a$$a$  — вершина, расстояния от которой ищутся
• $U$$U$  — множество посещённых вершин
• $d[u]$$d[u]$  — по окончании работы алгоритма равно длине кратчайшего пути из $a$$a$  до вершины $u$$u$ 
• $p[u]$$p[u]$  — по окончании работы алгоритма содержит кратчайший путь из $a$$a$  в $u$$u$ 
• $v$$v$  — текущая вершина, рассматриваемая алгоритмом

Код реализации алгоритмаПравить

Ниже приведён код реализации алгоритма на языке программирования 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);
				}
			}
		}
	}
}

ПсевдокодПравить

Присвоим

$d[a]\leftarrow <!--\; \leftarrow \; -->0,p[a]\leftarrow <!--\; \leftarrow \; -->0$$d[a]\gets 0,\ p[a]\gets 0$ 

Для всех $u\in <!--\; \in \; -->V$$u\in V$  отличных от $a$$a$  присвоим $d[u]\leftarrow <!--\; \leftarrow \; -->\mathrm{\infty <!--\; \infty \; -->}$$d[u]\gets \infty$ .

Пока $\mathrm{\exists <!--\; \exists \; -->}v\notin <!--\; \notin \; -->U$$\exists v\notin U$ . Пусть $v\notin <!--\; \notin \; -->U$$v\notin U$  — вершина с минимальным $d[v]$$d[v]$  занесём $v$$v$  в $U$$U$ 

Для всех $u\notin <!--\; \notin \; -->U$$u\notin U$  таких, что $vu\in <!--\; \in \; -->E$$vu\in E$ 

если $d[u]>d[v]+w[vu]$$d[u]>d[v]+w[vu]$  то

изменим $d[u]\leftarrow <!--\; \leftarrow \; -->d[v]+w[vu]$$d[u]\gets d[v]+w[vu]$ 

изменим $p[u]\leftarrow <!--\; \leftarrow \; -->(p[v],u)$$p[u]\gets (p[v],u)$ 

ОписаниеПравить

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

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

На каждом шаге цикла мы ищем вершину $v$$v$  с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины $u$$u$ . Если в них (в $u$$u$ ) расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 $d[i]=\mathrm{\infty <!--\; \infty \; -->}$$d[i]=\infty$ . Последний случай возможен тогда и только тогда, когда граф G несвязный.

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

Пусть $l(v)$$l(v)$  — длина кратчайшего пути из вершины $a$$a$  в вершину $v$$v$ . Докажем по индукции, что в момент посещения любой вершины $z$$z$  выполняется равенство $d(z)=l(z)$$d(z)=l(z)$ .

База. Первой посещается вершина $a$$a$ . В этот момент $d(a)=l(a)=0$$d(a)=l(a)=0$ .

Шаг. Пусть мы выбрали для посещения вершину $z\ne <!--\; \ne \; -->a$$z\neq a$ . Докажем, что в этот момент $d(z)=l(z)$$d(z)=l(z)$ . Для начала отметим, что для любой вершины $v$$v$  всегда выполняется $d(v)\ge <!--\; \ge \; -->l(v)$$d(v)\geq l(v)$  (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть $P$$P$  — кратчайший путь из $a$$a$  в $z$$z$ . Вершина $z$$z$  находится на $P$$P$  и не посещена. Поэтому множество непосещённых вершин на $P$$P$  непусто. Пусть $y$$y$  — первая непосещённая вершина на $P$$P$ , $x$$x$  — предшествующая ей (следовательно, посещённая). Поскольку путь $P$$P$  кратчайший, его часть, ведущая из $a$$a$  через $x$$x$  в $y$$y$ , тоже кратчайшая, следовательно $l(y)=l(x)+w(xy)$$l(y)=l(x)+w(xy)$ .

По предположению индукции, в момент посещения вершины $x$$x$  выполнялось $d(x)=l(x)$$d(x)=l(x)$ , следовательно, вершина $y$$y$  тогда получила метку не больше чем $d(x)+w(xy)=l(x)+w(xy)=l(y)$$d(x)+w(xy)=l(x)+w(xy)=l(y)$ . Следовательно, $d(y)=l(y)$$d(y)=l(y)$ . Если $z=y$$z=y$ , то индукционный переход доказан. Иначе, поскольку сейчас выбрана вершина $z$$z$ , а не $y$$y$ , метка $z$$z$  минимальна среди непосещённых, то есть $d(z)\le <!--\; \le \; -->d(y)=l(y)\le <!--\; \le \; -->l(z)$$d(z)\leq d(y)=l(y)\leq l(z)$ . Комбинируя это с $d(z)\ge <!--\; \ge \; -->l(z)$$d(z)\geq l(z)$ , имеем $d(z)=l(z)$$d(z)=l(z)$ , что и требовалось доказать.

Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент $d=l$$d=l$  для всех вершин.

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

Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещённых вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество рёбер в графе G.

• В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается всё множество вершин, а для хранения величин d используется массив, время работы алгоритма есть $O(n^2)$$O(n^{2})$ . Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма $O(n^2+m)$$O(n^{2}+m)$ , но, так как $m\le <!--\; \le \; -->n(n-<!--\; -\; -->1)$$m\leq n(n-1)$ , оно составляет $O(n^2)$$O(n^{2})$ .

• Для разреженных графов (то есть таких, для которых m много меньше n²) непосещённые вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время удаления вершины из $\stackrel{¯<!--\; ¯\; -->}{U}$$\overline U$  станет $\log <!--\; \; -->n$$\log n$  при том, что время модификации $d[i]$$d[i]$  возрастёт до $\log <!--\; \; -->n$$\log n$ . Так как цикл выполняется порядка n раз, а количество смен меток не больше m, время работы такой реализации — $O(n\log <!--\; \; -->n+m\log <!--\; \; -->n)$$O(n\log n+m\log n)$ .

• Если для хранения непосещённых вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за $O(\log <!--\; \; -->n)$$O(\log n)$ , а уменьшение значения в среднем за $O(1)$$O(1)$ , то время работы алгоритма составит $O(n\log <!--\; \; -->n+m)$$O(n\log n+m)$ . Однако согласно лекциям Алексеева и Таланова:

скрытые константы в асимптотических оценках трудоёмкости велики и использование фибоначчиевых куч редко оказывается целесообразным: обычные двоичные (d-ичные (англ.)) кучи на практике эффективнее.

Альтернативами им служат толстые кучи, тонкие кучи и кучи Бродала (англ.), обладающие теми же асимптотическими оценками, но меньшими константами.

См. такжеПравить

• Очередь с приоритетом (программирование)
• Минимальное остовное дерево
• Остовное дерево
• Задача о кратчайшем пути
• Алгоритм Борувки
• Алгоритм Краскала
• Алгоритм обратного удаления
• Алгоритм Прима

ЛитератураПравить

• Dijkstra E. W. A note on two problems in connexion with graphs (англ.) // Numer. Math / F. Brezzi — Springer Science+Business Media, 1959. — Vol. 1, Iss. 1. — P. 269—271. — ISSN 0029-599X; 0945-3245 — doi:10.1007/BF01386390
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
• Левитин А. В. Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 189—195. — 576 с. — ISBN 978-5-8459-0987-9

СсылкиПравить

• C. Анисимов. Как построить кратчайший маршрут между двумя точками.
• Реализация простейшего варианта алгоритма Дейкстры на e-maxx.ru
• Реализация варианта алгоритма Дейкстры для разреженных графов на e-maxx.ru
• Реализация варианта алгоритма Дейкстры с корневой эвристикой
• Алгоритм Дейкстры. Код программы на Python
• Пример на YouTube
• Dijkstra’s algorithm — реализация алгоритма на разных языках на Rosetta Code^[en].