Алгоритм дейкстра


Содержание

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

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

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

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

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

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

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

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

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

Пусть l(v) — длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z). База. Первой посещается вершина a. В этот момент d(a)=l(a)=0. Шаг. Пускай мы выбрали для посещения вершину . Докажем, что в этот момент d(z)=l(z). Для начала отметим, что для любой вершины v, всегда выполняется (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P — кратчайший путь из a в z, 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, её метка минимальна среди непосещённых, то есть . Комбинируя это с , имеем d(z)=l(z), что и требовалось доказать.

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

Алгоритм дейкстра

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

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

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

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

Неформальное объяснение

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

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

Обозначения

  • — множество вершин графа
  • — множество ребер графа
  • — вес (длина) ребра
  • — вершина, расстояния от которой ищутся
  • — множество посещенных вершин
  • — по окончании работы алгоритма равно длине кратчайшего пути из до вершины
  • — по окончании работы алгоритма содержит кратчайший путь из в

Псевдокод

Для всех отличных от

Пусть — вершина с минимальным занесём в Для всех таких, что если d[v] + w[vu]» border=»0″ /> то изменим изменим

Описание

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

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


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

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

Пусть l(v) — длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z).
База. Первой посещается вершина a. В этот момент d(a)=l(a)=0.
Шаг. Пускай мы выбрали для посещения вершину . Докажем, что в этот момент d(z)=l(z). Для начала отметим, что для любой вершины v, всегда выполняется (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P — кратчайший путь из a в z, 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, её метка минимальна среди непосещённых, то есть . Комбинируя это с , имеем d(z)=l(z), что и требовалось доказать.

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

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

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

  • В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d используется массив, время работы алгоритма есть . Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма , но, так как , оно составляет .
  • Для разреженных графов (то есть таких, для которых m много меньше n²) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время удаления вершины из станет , при том, что время модификации возрастет до . Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, скорость работы такой реализации .
  • Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за , а уменьшение значения в среднем за , то время работы алгоритма составит . Однако, согласно сайту intuit.ru, [3]

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

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

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

Алгоритм Дейкстры позволяет нам найти кратчайший путь между любыми двумя вершинами графа.

Он отличается от минимального остовного дерева тем, что кратчайшее расстояние между двумя вершинами может не включать все вершины графа.

Как работает алгоритм Дейкстры

Алгоритм Дейкстры работает на том основании, что любой подпуть B -> D кратчайшего пути A -> D между вершинами A и D также является кратчайшим путем между вершинами B и D.

Дейкстра использовал это свойство в противоположном направлении, т.е. мы переоцениваем расстояние каждой вершины от начальной вершины. Затем мы посещаем каждый узел и его соседей, чтобы найти кратчайший подпуть к этим соседям.

Алгоритм использует «жадный» подход в том смысле, что мы находим следующее лучшее решение, надеясь, что конечный результат является лучшим решением для всей задачи.

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

Проще начать с примера, а затем подумать об алгоритме.

Алгоритм Дейкстры. Псевдокод.

Нам нужно сохранять расстояние пути каждой вершины. Мы можем сохранить его в массиве размера v, где v — количество вершин.

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

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


Очередь с минимальным приоритетом может использоваться для эффективного получения вершины с наименьшим расстоянием пути.

Код для алгоритма Дейкстры

Реализация алгоритма Дейкстры в C ++ приведена ниже. Сложность кода может быть улучшена, но абстракции удобны для связи кода с алгоритмом.

Рекомендуем хостинг TIMEWEB

Рекомендуемые статьи по этой тематике

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

27.05.2020, 11:12

Алгоритм Дейкстры С++
Реализовать алгоритм поиска кратчайшего пути. Алгоритм Дейкстры. Представление графа – матрица.

Алгоритм Дейкстры
Пытаюсь сейчас его понять, как я понял сперва надо оставить матрицу смежности, и все возможные.

Илон Маск рекомендует:  Атрибут controls в HTML

Алгоритм Дейкстры
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а дальше-нет.

Алгоритм Дейкстры
Что-то у меня Дейкстра не работает. прошу помощи у вас. Сам уже часа 1.5 сижу и не могу найти.

Алгоритм Дейкстры
Здравствуйте. Есть код для нахождения длин от начальной вершины до всех остальных, не могу.

27.05.2020, 11:34 2 27.05.2020, 11:49 3 27.05.2020, 13:17 [ТС] 4

Спасибо огромное! Вы мне очень помогли

Добавлено через 1 час 16 минут

27.05.2020, 13:17
27.05.2020, 14:33 5

Либо хранить. Вверху есть строчку p[j] = p[j]+что-то там
Заводите еще один vector parent(n, -1);
И после этой строки вставляете parent[j] = i;

Вывод тогда будет таким

28.05.2020, 13:34 [ТС] 6
28.05.2020, 15:32 7

Решение

Leonsmoke, цитата с интернета : разумеется, обычно нужно знать не только длины кратчайших путей, но и получить сами пути. Покажем, как сохранить информацию, достаточную для последующего восстановления кратчайшего пути из s до любой вершины. Для этого достаточно так называемого массива предков: массива p[], в котором для каждой вершины v != s хранится номер вершины p[v], являющейся предпоследней в кратчайшем пути до вершины v. Здесь используется тот факт, что если мы возьмём кратчайший путь до какой-то вершины v, а затем удалим из этого пути последнюю вершину, то получится путь, оканчивающийся некоторой вершиной p[v], и этот путь будет кратчайшим для вершины p[v]. Итак, если мы будем обладать этим массивом предков, то кратчайший путь можно будет восстановить по нему, просто каждый раз беря предка от текущей вершины, пока мы не придём в стартовую вершину s — так мы получим искомый кратчайший путь, но записанный в обратном порядке.

Осталось понять, как строить этот массив предков. Однако это делается очень просто: при каждой успешной релаксации, т.е. когда из выбранной вершины v происходит улучшение расстояния до некоторой вершины to, мы записываем, что предком вершины to является вершина v:

Добавлено через 1 час 33 минуты
Leonsmoke, если на примере сообщения выше, первого способа Ромаха и моего кода из моего же, собсна,первого ответа, то как-то так :

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

Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами s и t при положительных длинах дуг. Этот алгоритм,. предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи.
Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны m вершин, ближайших к вершине s (близость любой вершины x к вершине s определяется длиной кратчайшего пути, ведущего из s в x). Пусть также известны сами кратчайшие пути, соединяющие вершину s с выделенными m вершинами). Покажем теперь, как может быть определена (m + 1)-я ближайшая к s вершина.
Окрасим вершину s и m ближайших к ней вершин. Построим для каждой неокрашенной вершины y пути, непосредственно соединяющие с помощью дуг (х, у) каждую окрашенную вершину х с у. Выберем из этих путей кратчайший, и будем считать его условно кратчайшим путем из вершины s в вершину y.
Какая же из неокрашенных вершин является (m + 1)-й ближайшей к s вершиной? Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины s в (m +1)-ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т. е. вершины, входящие в число m вершин, ближайших к вершине s.
Итак, если известны m ближайших к s вершин, то (m + 1)-я ближайшая к s вершина может быть найдена так, как это описано выше. Начиная с m = 0, описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины s к вершине t.
Имея в виду приведенные соображения, мы можем теперь формально описать алгоритм Дейкстры.


Алгоритм

      Каждой вершине X в ходе алгоритма присваивается число d(x), равное длине кратчайшего пути из вершины S в вершину X и включающем только окрашенные вершины. Положить d(s)=0 и d(x)=∞ для всех остальных вершин графа. Окрашиваем вершину S и полагаем y=S, где y – последняя окрашенная вершина.

    Каждый раз окрашивается вершина и дуга, заходящая в эту вершину. Окрашенные дуги не могут образовывать цикл, а образуют в исходном графе дерево с корнем (началом) в вершине s. Это дерево называют ориентированным деревом кратчайших путей. Путь из s в t принадлежит этому дереву. При поиске одного кратчайшего пути процедура наращивания завершается при достижении конечной вершины этого пути. Нам же необходимо получить все кратчайшие пути начинающиеся в вершине №1. Для этого процедуру наращивания ориентированного дерева продолжается до тех пор, пока все вершины не будут включены. Таким образом, мы получаем ориентированное дерево кратчайших путей, которое является покрывающим деревом графа.
    Иногда в графе имеются несколько кратчайших путей. Кратчайший путь будет единственным, если в алгоритме ни разу не возникает неоднозначность при окрашивании дуги.

    Отметим, что главным условием успешного применения алгоритма дейкстры к задаче на графе является неотрицательность длин дуг этого графа

    Алгоритм дейкстра

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

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

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

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

    Неформальное объяснение

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

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

    Обозначения

    • — множество вершин графа
    • — множество ребер графа

    • — вес (длина) ребра
    • — вершина, расстояния от которой ищутся
    • — множество посещенных вершин
    • — по окончании работы алгоритма равно длине кратчайшего пути из до вершины
    • — по окончании работы алгоритма содержит кратчайший путь из в

    Псевдокод

    Для всех отличных от

    Пусть — вершина с минимальным занесём в Для всех таких, что если d[v] + w[vu]» border=»0″ /> то изменим изменим

    Описание

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

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

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

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

    Пусть l(v) — длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z).
    База. Первой посещается вершина a. В этот момент d(a)=l(a)=0.
    Шаг. Пускай мы выбрали для посещения вершину . Докажем, что в этот момент d(z)=l(z). Для начала отметим, что для любой вершины v, всегда выполняется (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P — кратчайший путь из a в z, 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, её метка минимальна среди непосещённых, то есть . Комбинируя это с , имеем d(z)=l(z), что и требовалось доказать.

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

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

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

    • В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d используется массив, время работы алгоритма есть . Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма , но, так как , оно составляет .
    • Для разреженных графов (то есть таких, для которых m много меньше n²) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время удаления вершины из станет , при том, что время модификации возрастет до . Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, скорость работы такой реализации .
    • Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за , а уменьшение значения в среднем за , то время работы алгоритма составит . Однако, согласно сайту intuit.ru, [3]

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

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

    Алгоритм Дейкстры — Dijkstra’s algorithm


    Алгоритм Дейкстры
    Учебный класс алгоритм поиска
    Структура данных график
    производительность наихудшего случая О ( | Е | + | В | журнал ⁡ | В | )
    График и дерево
    алгоритмы поиска
    • α-β
    • A *
    • B *
    • Откат
    • Луч
    • Беллмана-Форда
    • Лучший первый
    • Двунаправленный
    • Борувка
    • Отделение и оценка
    • BFS
    • британский музей
    • D *
    • ДФС
    • Дейкстра
    • Эдмондс
    • Флойд-Воршалл
    • поиск Fringe
    • скалолазание
    • ИДА*
    • Итерационное углубление
    • Джонсон
    • точка Перейти
    • Крускала
    • Лексикографическое BFS
    • LPA *
    • чопорный
    • SMA *
    Объявления
    • алгоритмы Graph
    • алгоритмы поиска
    • Список алгоритмов на графах
    похожие темы
    • динамическое программирование
    • График обхода
    • Дерево обхода
    • Поиск игр

    Алгоритм Дейкстров (или кратчайший путь Дейкстров Первого алгоритм , алгоритм SPF ) представляет собой алгоритм для нахождения кратчайших путей между узлами в графе , который может представлять собой, например, дорожную сеть. Он был задуман ученым Дейкстром в 1956 году и опубликовал три года спустя.

    Алгоритм существует во многих вариантах; Оригинальный вариант Дейкстров найден кратчайший путь между двумя узлами, но более распространенным вариантом фиксирует один узел в качестве узла «источника» и находит кратчайшие пути от источника до всех остальных узлов в графе, производя дерево кратчайшего пути .

    Для заданного исходного узла в графе, алгоритм находит кратчайший путь между этим узлом и любым другим. Он также может быть использован для нахождения кратчайшего пути от одного узла к одному узлу назначения путем остановки алгоритма , как только самый короткий путь к узлу назначения был определен. Например, если узлы графа представляют города и затраты на край дорожки представляют собой движение расстояния между парами городов , соединенных прямым дорогой, алгоритм Дейкстры может быть использован , чтобы найти кратчайший маршрут между одним городом и всеми другими городами. В результате, самый короткий путь алгоритм широко используются в сетевых протоколах маршрутизации , в первую очередь IS-IS (Межшлюзовая систему) и кратчайший путь ( OSPF ). Он также используется в качестве подпрограммы в других алгоритмов , таких как Джонсон .

    Алгоритм Дейкстры использует метки, положительные целые или действительные числа, которые имеют строгий слабый порядок определен. Интересно, что Дейкстр может быть обобщен использовать метки, определенные в любом виде, при условии, что они имеют строгий частичный порядок, определенный, и при условии, что последующие этикетки (последующие этикетки производятся при прохождении ребра) монотонно не убывает. Это обобщение называется алгоритмом кратчайшего пути Родового Дейкстра.

    Оригинальный алгоритм Дейкстров не использует очередь мин приоритета и работает в время (где это число узлов). Идея этого алгоритма также приведена в Leyzorek и др. 1957 . Реализация на основе мин-приоритетной очереди , реализуемой в куче Фибоначчи и работает в (где это число ребер) происходит из — за Fredman & Tarjan 1984 . Это асимптотически самый быстрый известный из одного источника алгоритм кратчайшего пути для произвольных ориентированных графов с неограниченными неотрицательными весами. Тем не менее, специализированные случаи (такие как ограниченные / целые весы, направленные ациклические графы и т.д.) на самом деле могут быть улучшены дополнительно , как описано в § Специализированных вариантов . О ( | В | 2 ) <\ Displaystyle O (| V | ^ <2>)> | В | <\ Displaystyle | V |>О ( | Е | + | В | журнал ⁡ | В | ) <\ Displaystyle O (| E | + | В | \ войти | V |)>| Е |

    В некоторых областях, искусственного интеллекта , в частности, алгоритм Дейкстры или его вариант известен как равномерном поиск стоимости и сформулировали как пример более общей идеи лучше всего первого поиска .

    содержание

    история

    Что это самый короткий путь путешествовать из Роттердама в Гронинген , в целом: от данного города в данный город. Это алгоритм кратчайшего пути , который я разработал примерно двадцать минут. Однажды утром я ходил по магазинам в Амстердаме с моим молодым fiancée, и усталостью, мы сели на террасе кафе , чтобы выпить чашечку кофе , и я просто думал о том, смогу ли я это сделать, и тогда я разработал алгоритм кратчайшего пути , Как я сказал, это было двадцать минут изобретение. На самом деле, она была опубликована в ’59, три года конца. Издание остается читаемым, это, на самом деле, очень приятно. Одна из причин , по которым так приятно было , что я разработал без карандаша и бумаги. Позже я узнал , что один из преимуществ проектирования без карандаша и бумаги , что вы почти вынуждены избегать всех преодолимые сложности. В конце концов , что алгоритм стал, к моему большому удивлению, один из краеугольных камней моей славы.

    Дейкстра подумал о кратчайшем пути проблемах при работе в Математическом центре в Амстердаме в 1956 году в качестве программиста , чтобы продемонстрировать возможности нового компьютера под названием ARMAC. Его цель состояла в том , чтобы выбрать как проблему и решение (которое будет произведено с помощью компьютера) , что невычислительных люди могли понять. Он разработал алгоритм кратчайшего пути , а затем реализовать его ARMAC на несколько упрощенных транспортную карту 64 городов в Нидерландах (64, так что 6 бит будет достаточно для кодирования городского номера). Год спустя, он наткнулся на другую проблему от аппаратных инженеров , работающих на следующий компьютер института: минимизировать количество провода для подключения к разъемам на задней панели аппарата. В качестве решения, он вновь открыл алгоритм , известный как минимальный алгоритм остовного дерева Прима (известный ранее Ярник , а также переоткрыт Прима). Дейкстра опубликовал алгоритм в 1959 году, через два года после того, как чопорная 29 лет после того, как Ярник.

    Алгоритм

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

    1. Отметить все узлы Непосещенные. Создать набор всех непосещенных узлов называются непосещенное множество .
    2. Присвоение каждого узел предварительного значения расстояния: установить его в ноль для нашего исходного узла и к бесконечности для всех других узлов. Установите начальный узел в качестве тока.
    3. Для текущего узла, рассмотрим все его непосещенных соседей и рассчитать их ориентировочные расстояния через текущий узел. Сравните вновь вычисленного предварительное расстояние до текущего заданного значения , и назначить меньший. Например, если текущий узел отмечен на расстоянии 6, а ребро , соединяющее его с соседней B имеет длину 2, то расстояние до B через будет 6 + 2 = 8. Если B ранее была отмечена расстояние больше , чем 8 затем изменить его до 8. в противном случае, сохранить текущее значение.
    4. Когда мы закончили , учитывая все непосещенные сосед текущего узла, отметьте текущий узел как посещенный и удалить его из Непосещенного набора . Посещаемой узел никогда не будет проверяться снова.
    5. Если узел назначения был отмечен посетил (при планировании маршрута между двумя конкретными узлами) , или если наималейшее ориентировочное расстояние между узлами в Непосещенных наборе равна бесконечность (при планировании полного обхода, возникает , когда нет никакой связи между исходным узлом а остальные узлы непосещенные), затем останавливается. Алгоритм завершен.
    6. В противном случае, выберите Непосещенные узел, помеченный с наименьшим предварительным расстоянием, установить его в качестве нового «текущего узла», и вернуться к шагу 3.

    При планировании маршрута, это на самом деле не нужно ждать, пока узел назначения не «посетил», как описано выше: алгоритм может остановиться, как только узел назначения имеет наименьшее ориентировочное расстояние между всеми «непосещенных» узлов (и, следовательно, может быть выбран в качестве следующий «ток»).

    Описание

    Предположим , что вы хотели бы найти кратчайший путь между двумя пересечениями на карте города: в начальной точке и назначения . Алгоритм Дейкстров сначала отмечает расстояние (от начальной точки) для любого другого пересечения на карте с бесконечностью . Это делается не означает , существует бесконечное расстояние, но отметить , что эти перекрестки еще не посетили; некоторые варианты этого метода просто оставить расстояния пересечений непомеченными . Теперь, на каждой итерации, выберите текущее пересечение . Для первой итерации, текущее пересечение будет отправной точкой, а расстояние до него (метка пересечение в) будет ноль . Для последующих итераций (после первого), текущее пересечение будет ближе непосещенная пересечение к исходной точке (это будет легко найти).

    Из текущего перекрестка, обновить расстояние до каждых Непосещенных пересечений, которая непосредственно связаны с ним. Это делается путем определения суммы расстояния между непосещенным пересечением и значением текущего пересечения и переименованием неподсоединенного пересечения с этим значением (сумма), если оно меньше , чем ее текущее значение. В сущности, пересечение перемаркированное , если путь к нему через текущее пересечение короче , чем ранее известные пути. Для облегчения идентификации кратчайшего пути, карандашом, отметьте дорогу со стрелкой , указывающей на перемаркированные пересечения , если метка / переименуйте его и стереть все другие, связанные с этим. После того, как вы обновили расстояние до каждого соседнего перекрестка , отметьте текущее пересечение , как побывал , и выберите Непосещенные пересечение с минимальным расстоянием (от начальной точки) — или самого низких маркированной в качестве текущего пересечения. Пересечения отмечены как посещенные метят кратчайший путь от начальной точки до него и не будет повторно или возвращен.

    Продолжайте этот процесс обновления соседних перекрестков с кратчайшими расстояниями, то маркировкой тока пересечения как посещенные и перемещением на ближайшие Непосещенные пересечения , пока вы не отметили назначения как посещенные. После того, как вы отметили назначение , как посетил (как в случае с любым посещаемым пересечением) вы определили самый короткий путь к нему, от начальной точки, и может проследить свой путь назад, следуя стрелкам в обратном направлении ; в реализации алгоритма, это обычно делается (после того , как алгоритм достиг узел назначения), следуя родитель узлов связи от узла назначения до стартового узла; Именно поэтому мы также следить за родителем каждого узла.

    Этот алгоритм не делает никаких попыток прямого «разведку» к месту назначения, как можно было бы ожидать. Скорее всего, единственным фактором при определении очередного «текущего» пересечение является его расстояние от начальной точки. Таким образом, этот алгоритм расширяется наружу от начальной точки, в интерактивном режиме с учетом каждый узла, который находится ближе по пути кратчайшего расстояния, пока она не достигнет места назначения. Когда понимать таким образом, ясно, как алгоритм обязательно находит самый короткий путь. Тем не менее, он также может выявить одну из слабостей алгоритма: его относительная медлительность в некоторых топологиях.

    ПСЕВДОКОД

    В последующем алгоритме, код U ← вершину в Q с мин дист [и] , ищет вершины ¯u в вершине множества Q , который имеет наименьшее DIST [ U ] значение. длина ( U , V ) возвращает длину ребра , соединяющее (т.е. расстояние между) двумя соседними узлами- ¯u и v . Переменная альт на линии 18, длина пути от корневого узла к соседнему узлу V , если оно было пройти через ц . Если этот путь короче , чем текущий кратчайший путь , записанный на V , что путь тока заменяется этой альт путем. Предыдущий массив заполняется указателем на «следующий переход» узел на исходный графике , чтобы получить кратчайший путь к источнику.

    Если мы заинтересованы только в кратчайшем пути между вершинами источником и целями , мы можем прекратить поиск после строки 15 , если у = цель . Теперь мы можем прочитать кратчайший путь от источника к целевому пути обратной итерации:

    Теперь последовательность S список вершин , составляющих один из кратчайших путей от источника к целевому , или пустой последовательности , если не существует никакого пути.


    Более общая задача будет найти все кратчайшие пути между источником и мишенью (там может быть несколько различных них одинаковой длиной). Тогда вместо того , чтобы хранить только один узел в каждой записи пред [] мы будем хранить все узлы , удовлетворяющие условие релаксации. Например, если оба г и источник подключение к целевому и оба они лежат на разных кратчайших через мишень (поскольку стоимость кромки одинакова в обеих случаях), то мы добавим как г и источник , чтобы предыдущий [ цель ] . Когда алгоритм завершается, пред [] структура данных будет фактически описывает график , который представляет собой подмножество исходного графа с некоторыми удаленными краями. Его ключевое свойство будет то , что если алгоритм был запущен с некоторым начальным узлом, то каждый путь от этого узла к любому другому узлу в новом графе будет кратчайший путем между этими узлами в исходном графе, и все пути этой длиной от исходный граф будет присутствовать в новом графе. Тогда на самом деле найти все эти кратчайшие пути между двумя заданными узлами мы могли бы использовать алгоритм поиска пути на новом графике, например, поиска в глубину .

    Использование очереди приоритета

    Очереди мин-приоритетом является абстрактным типом данных , который обеспечивает 3 основные операции: add_with_priority () , decrease_priority () и extract_min () . Как упоминалось ранее, используя такую структуру данных , может привести к более быстрому времени вычислений , чем при использовании основной очереди. Следует отметить, что Фибоначчи куча ( Фредман & Tarján 1984 ) или очередь Бродала предлагает оптимальные реализации для этих 3 -х операций. Поскольку алгоритм немного отличается, мы упоминаем его здесь, в псевдо-коде , а также:

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

    Другие структуры данных могут быть использованы для достижения еще более быстрое время вычислений на практике.

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

    Доказательство алгоритма Дейкстры строится индукцией по числу посещенных узлов.

    Инвариантная гипотеза : Для каждого посещаемого узла V , расстояние [v] считается кратчайшее расстояние от источника до V ; и для каждого узла непосещенных U , расстояние [U] предполагается кратчайшее расстояние при движении только через посещенных узлов, от источника к ц . Это предположение рассматривается только , если существует путь, в противном случае расстояние устанавливается на бесконечность. (Примечание: мы не предполагаем , расст [и] является фактическим кратчайшим расстоянием для непросмотренных узлов)

    Базовый случай, когда есть только один узел побывал, а именно начальный узел источник , причем в этом случае гипотеза тривиальная .

    В противном случае, предположим , что гипотезу о п-1 посещенных узлов. В этом случае, мы выбираем ребро вю , где у имеет наименьшее DIST [U] любых непосещенных узлов и край вю таково , что расстояние [и] = расстояние [v] + длина [v, и] . расстояние [U] считается кратчайшее расстояние от источника до U , потому что , если бы существовал более короткий путь, и если вес был первый непосещенная узел на этом пути , то с помощью исходной гипотезы дист [ш] > расстояние [U] , которая создает противоречие. Точно так же , если существует более короткий путь к U без использования непосещенные узлов, и если последний , но один узел на этом пути были ж , тогда мы имели бы DIST [U] = дист [ш] + длина [ж, и] , а также противоречие.

    После обработки U она все равно будет верно , что для каждого непосещенных узлов ш , дист [ж] будет кратчайшее расстояние от источника до ж , используя только посещенных узлов, так как если бы более короткий путь , который не проходит U мы имеем нашел его раньше, и если бы был более короткий путь , используя U мы обновили его при обработке U .

    Продолжительность

    Границы времени работы алгоритма Дейкстры на графе с ребрами Е и вершин V можно выразить как функцию от числа ребер, обозначенных , и числа вершин, обозначаемой , используя большой-O обозначения . Как крепко связанное возможно , зависит от того , как вершина набора Q выполняется. В дальнейшем верхние границы можно упростить , так как это для любого графа, но это упрощение не учитывает тот факт , что в некоторых задачах, другие верхние границы могут удерживать. | Е | <\ Displaystyle | E |>| В | <\ Displaystyle | V |>| Е | <\ Displaystyle | E |>О ( | В | 2 ) <\ Displaystyle O (| V | ^ <2>)> | Е |

    Для любой реализации множества вершин Q , время работы в

    где и являются Сложностями понижените ключ и выписки минимальных операций в Q , соответственно. Простейшая реализация алгоритма Дейкстры хранит множество вершин Q , как обычный связанный список или массив, и извлечь-минимум просто линейный поиск через все вершины Q . В этом случае, время работы является . T d К <\ Displaystyle T _ <\ mathrm <дк>>> T е м <\ Displaystyle T _ <\ mathrm <ет>>> О ( | Е | + | В | 2 ) знак равно О ( | В | 2 ) <\ Displaystyle O (| E | + | В | ^ <2>) = O (| V | ^ <2>)>

    Для разреженных графов , то есть графы с намного меньше , чем края, алгоритм Дейкстров может быть реализован более эффективен, сохраняя график в виде списков смежности и с помощью самобалансирующегося бинарного дерева поиска , двоичная кучи , спаривания кучи , или Фибоначчи куча в качестве приоритетной очереди , чтобы осуществить эффективное извлечение минимума. Для того, чтобы эффективно выполнять уменьшение действия ключа в двоичной куче, необходимо использовать вспомогательную структуру данных , которая отображает каждую вершину своей позиции в куче, и сохранить эту структуру вплоть до настоящего времени в качестве приоритета очереди Q изменений. С самобалансирующимся бинарным деревом поиска или двоичной кучей, алгоритм требует | В | 2 <\ Displaystyle | V | ^ <2>>

    Θ ( ( | Е | + | В | ) журнал ⁡ | В | )

    время в худшем случае (где обозначает двоичный логарифм ); для связных графов на этот раз связанный может быть упрощен . Куча Фибоначчи улучшает это журнал <\ Displaystyle \ лог>журнал 2 <\ Displaystyle \ лог _ <2>> Θ ( | Е | журнал ⁡ | В | )

    О ( | Е | + | В | журнал ⁡ | В | ) ,

    При использовании двоичных куч, то средний случая , сложность времени ниже , чем в худшем случае: предполагающие затраты на крае рисуются независимо от общего распределения вероятностей , ожидаемое число уменьшения ключа операций ограниченно , что дает общее время работы О ( | В | журнал ⁡ ( | Е | / | В | ) ) <\ Displaystyle O (| V | \ лог (| Е | / | V |))>

    Практическая оптимизация и бесконечные графики

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

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

    Сложность этого алгоритма может быть выражена в качестве альтернативного способа для очень больших графов: когда С * есть длина кратчайшего пути от начального узла к любому узлу , удовлетворяющему «цель» предикат, каждое ребро имеет стоимость по меньшей мере , ε , и число соседей на узел ограниченно Ь , то в худшем случае время и пространство сложность алгоритма является как в O ( б 1 + ⌊ с * ​ / & epsi ; ⌋ ) .

    Дальнейшие оптимизации алгоритма Дейкстров для одной цели случае включают в себя двунаправленные варианты, целенаправленные варианты , такие как A * алгоритм (см § Смежных проблем и алгоритмы ), график обрезка , чтобы определить , какие узлы, вероятно, образуют средний сегмент кратчайших (достигнуть на основе маршрутизация), и иерархические разложения входного графа , которые уменьшают Sт маршрутизация к соединению S и т к их соответствующим «транзитным узлам» с последующим кратчайшим путем вычислением между этими транзитными узлами с использованием «шоссе». Комбинации таких методов могут быть необходимы для оптимальной производительности на практическую конкретных проблемах.

    Специализированные варианты

    Когда дуговые веса небольшие целые числа (ограниченные параметром C ), A очереди приоритетов монотонной может быть использован для ускорения алгоритма Дейкстры. Первый алгоритм этого типа был алгоритмом циферблата , который использовал очередь ведра , чтобы получить время работы , которое зависит от взвешенного диаметра графа с целыми весами ребер ( набор 1969 ). Использование дерева Ван Эмд Боаса в качестве приоритетной очереди приносит сложность к ( Ahuja и др. , 1990 ). Еще одна интересная реализация на основе сочетания новой натальной кучи и хорошо известной кучи Фибоначчи работает во времени ( Ахаджа и др. 1990 ). Наконец, лучшие алгоритмы в этом особом случае являются следующими. Алгоритм задается ( Thorup 2000 ) работает в время и алгоритм задается ( Раман 1997 ) работает в время. О ( | Е | + диам ⁡ ( г ) ) <\ Displaystyle O (| E | + \ OperatorName <диам>(G))> О ( | Е | журнал ⁡ журнал ⁡ С ) <\ Displaystyle O (| E | \ Журнал \ Журнал C)>О ( | Е | + | В | журнал ⁡ С ) <\ Displaystyle O (| E | + | В | <\ SQRT <\ войти C>>)> О ( | Е | журнал ⁡ журнал ⁡ | В | ) <\ Displaystyle O (| E | \ войти \ войти | V |)>О ( | Е | + | В | мин < ( журнал ⁡ | В | ) 1 / 3 + ε , ( журнал ⁡ С ) 1 / 4 + ε >) <\ Displaystyle O (| E | + | В | \ мин \ <(\ войти | V |) ^ <1>, (\ войти C) ^ <1>\>) >

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

    В частном случае целых весов и неориентированных связных графов, алгоритм Дейкстры может быть полностью противопоставить линейный алгоритм сложности, дается формулой ( Thorup 1999 ). О ( | Е | )


    Связанные проблемы и алгоритмы

    Функциональность оригинального алгоритма Дейкстры может быть расширена с помощью различных модификаций. Например, иногда желательно, чтобы представить решения, которые меньше, чем математически оптимальные. Чтобы получить ранжированный список менее чем оптимальные решения, оптимальное решение сначала вычисляется. Одна кромка появляется в оптимальном решении удаляются из графика, и оптимальное решение для этого нового графика вычисляются. Каждое ребро исходного раствора подавляется, в свою очередь, и новый кратчайший путь вычисляется. Вторичные растворы затем ранжируются и представлены после первого оптимального решения.

    Алгоритм Дейкстры, как правило, принцип работы за протоколы состояния канала , OSPF и IS-IS является наиболее распространенными из них.

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

    A * алгоритм является обобщением алгоритма Дейкстры , что сокращает размер подграфа , которые должны быть изучены, если имеется дополнительная информация , которая обеспечивает нижнюю границу на «расстояние» до цели. Такой подход можно рассматривать с точки зрения линейного программирования : есть естественная линейная программа для вычисления кратчайших путей , и решения его двойной линейной программы возможны тогда и только тогда , когда они образуют последовательную эвристику (говоря грубо, так как условные знака отличаются с места на место в литературе). Это выполнимо двойной / последовательный эвристический определяет неотрицательное снижение стоимости и А *, по существу , работает алгоритм Дейкстры с этим снижение затрат. Если двойной удовлетворяет слабому условию приемлемости , то А * вместо более родственным алгоритма Беллмана-Форда.

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

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

    Быстрый метод походный можно рассматривать как непрерывный вариант алгоритма Дейкстры , который вычисляет геодезический расстояние на треугольной сетке.

    Динамическая перспектива программирования

    Из динамического программирования точки зрения, алгоритм Дейкстры является последовательной схемой аппроксимации , которая решает динамическое программирование функционального уравнение для кратчайшего пути задачи по достигающему методу.

    На самом деле, объяснение Дейкстры логики позади алгоритма, а именно

    Задача 2. Найти путь минимальной общей длины между двумя заданными узлами и . п <\ Displaystyle Р>Q

    Мы используем тот факт , что, если это узел на минимальном пути от к , знание последних предполагает знание минимального пути от к . р <\ Displaystyle R>п <\ Displaystyle Р>Q <\ Displaystyle Q>п <\ Displaystyle Р>р

    это парафраз Беллмана известного принципа оптимальности в контексте кратчайшего пути проблемы.

    Реализации алгоритмов/Алгоритм Дейкстры

    Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm ) — алгоритм на графах для нахождения кратчайшего расстояния от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

    C++ [ править ]

    • visited — массив посещенных вершин( индекс равен номеру вершины);
    • w — матрицы путей(хранит вес ребер), где несуществующие ребра имеют бесконечный вес;
    • D — массив минимальных путей;
    • INT_MAX — Максимальный размер типа int, принимаемый за бесконечность;
    • st — номер источника

    Python 3 [ править ]

    • N — количество вершин;
    • S — номер стартовой вершины (отсчитывая от нуля);
    • matrix — матрица смежности исходного графа, где несуществующие рёбра имеют бесконечный вес;
    • В данном случае бесконечность равна 1000000;

    Алгоритм Дейкстры для разреженных графов

    Тема: «Aлгоритмы нахождения кратчайшего пути в графе»

    Наверняка многим сейчас будет интересно услышать несколько важнейших алгоритмов, решающих задачи о кратчайших путях в графах (как-никак, необходимо сдавать 5 ЛР).

    Итак, для начала необходимо сформулировать определения и задачу.
    Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
    Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
    Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.

    Считаем, что в графе n вершин и m рёбер.
    Пойдём от простого к сложному.

    Алгоритм Флойда-Уоршела

    Находит расстояние от каждой вершины до каждой за количество операций порядка n^3. Веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер (иначе мы можем ходить по нему сколько душе угодно и каждый раз уменьшать сумму, так не интересно).
    В массиве d[0… n — 1][0… n — 1] на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в качестве «пересадочных» в пути мы будем использовать вершины с номером строго меньше i — 1 (вершины нумеруем с нуля). Пусть идёт i-ая итерация, и мы хотим обновить массив до i + 1-ой. Для этого для каждой пары вершин просто попытаемся взять в качестве пересадочной i — 1-ую вершину, и если это улучшает ответ, то так и оставим. Всего сделаем n + 1 итерацию, после её завершения в качестве «пересадочных» мы сможем использовать любую, и массив d будет являться ответом.
    n итераций по n итераций по n итераций, итого порядка n^3 операций.

    прочитать g // g[0 . n — 1][0 . n — 1] — массив, в котором хранятся веса рёбер, g[i][j] = 2000000000, если ребра между i и j нет

    if d[j][k] > d[j][i — 1] + d[i — 1][k]

    d[j][k] = d[j][i — 1] + d[i — 1][k]

    Алгоритм Форда-Беллмана

    Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n * m. Аналогично предыдущему алгоритму, веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер.
    Заведём массив d[0… n — 1], в котором на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в путь должно входить строго меньше i рёбер. Если таких путей до вершины j нет, то d[j] = 2000000000 (это должна быть какая-то недостижимая константа, «бесконечность»). В самом начале d заполнен 2000000000. Чтобы обновлять на i-ой итерации массив, надо просто пройти по каждому ребру и попробовать улучшить расстояние до вершин, которые оно соединяет. Кратчайшие пути не содержат циклов, так как все циклы неотрицательны, и мы можем убрать цикл из путя, при этом длина пути не ухудшится (хочется также отметить, что именно так можно найти отрицательные циклы в графе: надо сделать ещё одну итерацию и посмотреть, не улучшилось ли расстояние до какой-нибудь вершины). Поэтому длина кратчайшего пути не больше n — 1, значит, после n-ой итерации d будет ответом на задачу.
    n итераций по m итераций, итого порядка n * m операций.

    прочитать e // e[0 . m — 1] — массив, в котором хранятся рёбра и их веса (first, second — вершины, соединяемые ребром, value — вес ребра)

    if d[e[j].second] > d[e[j].first] + e[j].value

    d[e[j].second] = d[e[j].first] + e[j].value

    if d[e[j].first] > d[e[j].second] + e[j].value

    d[e[j].first] = d[e[j].second] + e[j].value

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

    Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n^2. Все веса неотрицательны.
    На каждой итерации какие-то вершины будут помечены, а какие-то нет. Заведём два массива: mark[0… n — 1] — True, если вершина помечена, False иначе, d[0… n — 1] — для каждой вершины будет храниться длина кратчайшего пути, проходящего только по помеченным вершинам в качестве «пересадочных». Также поддерживается инвариант того, что для помеченных вершин длина, указанная в d, и есть ответ. Сначала помечена только вершина 0, а g[i] равно x, если 0 и i соединяет ребро весом x, равно 2000000000, если их не соединяет ребро, и равно 0, если i = 0.
    На каждой итерации мы находим вершину, с наименьшим значением в d среди непомеченных, пусть это вершина v. Тогда значение d[v] является ответом для v. Докажем. Пусть, кратчайший путь до v из 0 проходит не только по помеченным вершинам в качестве «пересадочных», и при этом он короче d[v]. Возьмём первую встретившуюся непомеченную вершину на этом пути, назовём её u. Длина пройденной части пути (от 0 до u) — d[u]. len >= d[u], где len — длина кратчайшего пути из 0 до v (т. к. отрицательных рёбер нет), но по нашему предположению len меньше d[v]. Значит, d[v] > len >= d[u]. Но тогда v не подходит под своё описание — у неё не наименьшее значение d[v] среди непомеченных. Противоречие.
    Теперь смело помечаем вершину v и пересчитываем d. Так делаем, пока все вершины не станут помеченными, и d не станет ответом на задачу.
    n итераций по n итераций (на поиск вершины v), итого порядка n^2 операций.

    прочитать g // g[0 . n — 1][0 . n — 1] — массив, в котором хранятся веса рёбер, g[i][j] = 2000000000, если ребра между i и j нет

    if (not mark[i]) and ((v == -1) or (d[v] > d[i]))

    Алгоритм Дейкстры для разреженных графов

    Делает то же самое, что и алгоритм Дейкстры, но за количество операций порядка m * log(n). Следует заметить, что m может быть порядка n^2, то есть эта вариация алгоритма Дейкстры не всегда быстрее классической, а только при маленьких m.
    Что нам нужно в алгоритме Дейкстры? Нам нужно уметь находить по значению d минимальную вершину и уметь обновлять значение d в какой-то вершине. В классической реализации мы пользуемся простым массивом, находить минимальную по d вершину мы можем за порядка n операций, а обновлять — за 1 операцию. Воспользуемся двоичной кучей (во многих объектно-ориентированных языках она встроена). Куча поддерживает операции: добавить в кучу элемент (за порядка log(n) операций), найти минимальный элемент (за 1 операцию), удалить минимальный элемент (за порядка log(n) операций), где n — количество элементов в куче.
    Создадим массив d[0… n — 1] (его значение то же самое, что и раньше) и кучу q. В куче будем хранить пары из номера вершины v и d[v] (сравниваться пары должны по d[v]). Также в куче могут быть фиктивные элементы. Так происходит, потому что значение d[v] обновляется, но мы не можем изменить его в куче. Поэтому в куче могут быть несколько элементов с одинаковым номером вершины, но с разным значением d (но всего вершин в куче будет не более m, я гарантирую это). Когда мы берём минимальное значение в куче, надо проверить, является ли этот элемент фиктивным. Для этого достаточно сравнить значение d в куче и реальное его значение. А ещё для записи графа вместо двоичного массива используем массив списков.
    m раз добавляем элемент в кучу, получаем порядка m * log(n) операций.

    прочитать g // g[0 . n — 1] — массив списков, в i-ом списке хранятся пары: first — вершина, соединённая с i-ой вершиной ребром, second — вес этого ребра

    Алгоритм дейкстры и его реализация

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

    Считается, что понятие графа было введено в обиход в восемнадцатом веке Леонардом Эйлером. Именно он озвучил постановку и решение одной из классических задач этой теории – о семи мостах Кенигсберга. Для того чтобы объяснить объект этой теории, чаще всего пользуются такой аналогией, как передвижение между различными городами. Тогда граф на плоскости будет представлять собой всю схему маршрутов, где вершинами станут конкретные пункты (например, города), а ребрами – пути из одной вершины в другую (аналог дороги между городами). Алгоритм Дейкстры, кроме других способов, может дать решение этого вопроса.

    Одной из стандартных задач теории графов является та, в которой нужно определить оптимальный по затратам путь между двумя точками. Ее можно свести на плоскости к решению графа, в котором вершины – города — связаны между собой ребрами, что представляют собой возможные дороги. Причем каждая дорога имеет свою длину, следовательно, на проезд по ней придется потратить определенные средства. Эта сумма эквивалентна весу ребра на графе. Тогда задачу на практике можно сформулировать так: как проложить путь из одного города в другой, чтобы затратить на дорогу минимальные средства.

    Способы решения

    Для решения этой задачи были придуманы некоторые алгоритмы, которые стали широко известны в научном мире. Например, алгоритм Флойда – Уоршелла, Форда – Беллмана. Классическим способом нахождения решения является также алгоритм Дейкстры. Он может использоваться и для взвешенного (известен вес каждого ребра) графа, и для разреженного. Для нахождения окончательного пути нужно проделать несколько шагов.

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

    Смысл этого способа заключается в том, что обходятся все вершины, начиная с заданной, при этом каждой присваивается метка с некоторым значением. Затем в результат войдут те вершины, метки которых минимальны. На первом шаге исходной вершине присваивается метка со значением 0. Затем рассматриваются все следующие вершины, то есть те, в которые можно попасть из исходной. Им присваиваются метки, значение которых определяется как сумма исходника и веса пути. Из вершин следующего шага выбирается та, что имеет наименьшее значение метки, и изучаются все вершины, в которые из нее можно пройти, не используя промежуточных вершин. Определяется новое значение метки, равное метке вершины – исходника плюс вес пути. Если полученное значение меньше, чем метка вершины, то метка изменяется. В противном случае остается исходное значение. При этом в отдельном массиве, размерность которого равна количеству вершин графа, сохраняется результат оптимизации, по которому и определяется путь. Для реализации такого способа, как алгоритм Дейкстры, Pascal предлагает очень удобные средства. Алгоритм имеет то преимущество, что легко может быть положен в основу программы, которая имеет небольшой размер. Примеры таких программных продуктов легко найти в сети Интернет.

    Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL