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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Блок схема алгоритма Дейкстры.

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

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

Примеры[править | править вики-текст]

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

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

Формальное определение[править | править вики-текст]

Дан взвешенный ориентированный[1] граф G(V, E) без дуг отрицательного веса[2]. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

Неформальное объяснение[править | править вики-текст]

Dijkstra Animation.gif

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

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

Пример[править | править вики-текст]

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

Dijkstra graph0.PNG

Кружками обозначены вершины, линиями — пути между ними (рёбра графа). В кружках обозначены номера вершин, над рёбрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Dijkstra graph1.PNG

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Dijkstra graph2.PNG

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

Dijkstra graph3.PNG

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

Dijkstra graph5.PNG

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

Dijkstra graph6.PNG

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Dijkstra graph7.PNG

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

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

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

Dijkstra graph9.PNG

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

Dijkstra graph8.PNG

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

Dijkstra graph10.PNG

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

Dijkstra graph11.PNG

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

Dijkstra graph12.PNG Dijkstra graph13.PNG Dijkstra graph14.PNG

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

Алгоритм[править | править вики-текст]

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

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

Псевдокод[править | править вики-текст]

Присвоим d[a] \gets 0,\ p[a] \gets 0

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

присвоим d[u] \gets \infty

Пока \exists v \notin U

Пусть v \notin U — вершина с минимальным d[v]
занесём v в U
Для всех u \notin U таких, что vu \in E
если  d[u] > d[v] + w[vu] то
изменим d[u] \gets d[v] + w [vu]
изменим p[u] \gets p[v], u

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

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

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

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

Доказательство корректности[править | править вики-текст]

Пусть l(v) — длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z).
База. Первой посещается вершина a. В этот момент d(a)=l(a)=0.
Шаг. Пускай мы выбрали для посещения вершину z\ne a. Докажем, что в этот момент d(z)=l(z). Для начала отметим, что для любой вершины v, всегда выполняется d(v)\ge l(v) (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P — кратчайший путь из a в z. Вершина z находится на P и не посещена. Поэтому множество непосещённых вершин на P непусто. Пусть y — первая непосещённая вершина на P, x — предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть, ведущая из a через x в y, тоже кратчайшая, следовательно l(y)=l(x)+w(xy). По предположению индукции, в момент посещения вершины x выполнялось d(x)=l(x), следовательно, вершина y тогда получила метку не больше чем d(x)+w(xy)=l(x)+w(xy)=l(y). Следовательно, d(y)=l(y). Если z=y, то индукционный переход доказан. Иначе, поскольку сейчас выбрана вершина z а не y, метка z минимальна среди непосещённых, то есть d(z)\le d(y)=l(y)\le l(z). Комбинируя это с d(z)\ge l(z), имеем d(z)=l(z), что и требовалось доказать.

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

Сложность алгоритма[править | править вики-текст]

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

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

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

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

Реализация[править | править вики-текст]

Python3[править | править вики-текст]

Предполагается:

  • N — количество вершин;
  • S — номер стартовой вершины (отсчитывая от нуля);
  • matrix — матрица смежности исходного графа, где несуществующие рёбра имеют бесконечный вес;
  • В данном случае бесконечность равна 1000000;
def Dijkstra(N, S, matrix):
	valid = [True]*N        
	weight = [1000000]*N
	weight[S] = 0
	for i in range(N):
		min_weight = 1000001
		ID_min_weight = -1
		for i in range(len(weight)):
			if valid[i] and weight[i] < min_weight:
				min_weight = weight[i]
				ID_min_weight = i
		for i in range(N):
			if weight[ID_min_weight] + matrix[ID_min_weight][i] < weight[i]:
				weight[i] = weight[ID_min_weight] + matrix[ID_min_weight][i]
		valid[ID_min_weight] = False
	return weight

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

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

  • Dijkstra E. W. A note on two problems in connexion with graphs. // Numerische Mathematik. V. 1 (1959), P. 269—271
  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
  • Ананий В. Левитин. Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 189—195. — ISBN 0-201-74395-7.

Примечания[править | править вики-текст]

  1. Здесь частным случаем ориентированного графа являются неориентированный и смешенный («частично ориентированный») графы.
  2. Для графа с отрицательными весами применяется более общий алгоритм — Алгоритм Дейкстры с потенциалами
  3. Владимир Алексеев, Владимир Таланов, Курс «Структуры данных и модели вычислений», Лекция № 7: Биномиальные и фибоначчиевы кучи // 26.09.2006, Интуит.ру
  4. Владимир Алексеев, Владимир Таланов, Курс «Структуры данных и модели вычислений», Лекция № 8: Тонкие кучи // 26.09.2006, Интуит.ру