Как работает алгоритм дейкстры
Алгоритмы поиска
кратчайшего пути
Нахождения наименьшего
остового дерева
Максимальные потоки
и паросочетания
Алгоритм Дейкстры
Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
Формальное описание
В строке 1 производится обычная инициализация величин d и pi, а в строке 2 инициализируется пустое множество вершин S. В этом алгоритме поддерживается инвариант, согласно которому в начале каждой итерации цикла while в строках 4-8 выполняется равенство Q = V — S. В строке 3 неубывающая очередь с приоритетами Q инициализируется таким образом, чтобы она содержала все вершины множества V; поскольку в этот момент S = 0, после выполнения строки 3 сформулированный выше инвариант выполняется. При каждой итерации цикла while в строках 4-8 вершина и извлекается из множества Q = V — S и добавляется в множество 5, в результате чего инвариант продолжает соблюдаться. (Во время первой итерации этого цикла u = s.) Таким образом, вершина и имеет минимальную оценку кратчайшего пути среди всех вершин множества V — 5. Затем строках 7-8 ослабляются все ребра (u, v), исходящие из вершины и. Если текущий кратчайший путь к вершине v может быть улучшен в результате прохождения через вершину и, выполняется ослабление и соответствующее обновление оценки величины d [v] и предшественника тг [v]. Обратите внимание, что после выполнения строки 3 вершины никогда не добавляются в множество Q и что каждая вершина извлекается из этого множества и добавляется в множество 5 ровно по одному разу, поэтому количество итераций цикла while в строках 4-8 равно | V|. Поскольку в алгоритме Дейкстры из множества V — S для помещения в множество 5 всегда выбирается самая «легкая» или «близкая» вершина, говорят, что этот алгоритм придерживается жадной стратегии.
Оценка сложности [вверх]
Время выполнения алгоритма Дейкстры зависит от реализации неубывающей очереди с приоритетами. Сначала рассмотрим случай, когда неубывающая очередь с приоритетами поддерживается за счет того, что все вершины пронумерованы от 1 до |V|. Атрибут d[v] просто помещается в элемент массива с индексом v. Каждая операция Insert и Decrease_Key (неявно присутствует в процедуре Relax) занимает время 0(1), а каждая операция Extract_Min — время О (V) (поскольку в ней производится поиск по всему массиву); в результате полное время работы алгоритма равно О (V 2 + Е) = О(V 2 ).
Если граф достаточно разреженный, в частности, если количество вершин и ребер в нем связаны соотношением Е = o(V 2 /lgV), с практической точки зрения целесообразно реализовать неубывающую очередь с приоритетами в виде бинарной неубывающей пирамиды. (важная деталь реализации заключается в том, что вершины и соответствующие им элементы пирамиды должны поддерживать идентификаторы друг друга.) Далее, каждая операция Extract_Min занимает время О (lg V), Как и раньше, таких операций |V|. Время, необходимое для построения неубывающей пирамиды, равно O(V). Каждая операция Decrease_Key занимает время O(lgV), и всего выполняется не более |Е| таких операций. Поэтому полное время выполнения алгоритма равно О ((V + Е) lg V), что равно О (Е*lg V), если все вершины достижимы из истока. Это время работы оказывается лучшим по сравнению со временем работы прямой реализации О (V 2 ), если Е = о (V 2 /lg V).
Пример работы алгоритма [вверх]
Визуализатор для алгоритма Дейкстры.
Алгоритм Дейкстры
Алгоритм Дейкстры — это метод, который находит кратчайший путь от одной вершины графа к другой. Граф — структура из точек-вершин, соединенных ребрами-отрезками. Его можно представить как схему дорог или как компьютерную сеть. Ребра — это связи, по ним можно двигаться от одной вершины к другой.
Освойте профессию «Data Scientist»
Графы используют для моделирования реальных объектов, а алгоритмы поиска пути — при их изучении, а также решении практических задач. Алгоритм Дейкстры работает для графов, у которых нет ребер с отрицательным весом, т.е. таких, при прохождении через которые длина пути как бы уменьшается.
В отличие от похожих методов, алгоритм Дейкстры ищет оптимальный маршрут от одной заданной вершины ко всем остальным. Попутно он высчитывает длину пути — суммарный вес ребер, по которым проходит при этом маршруте.
Читайте также Как выбрать IT-специальность в новых реалиях?
Кто пользуется алгоритмом Дейкстры
- Математики и другие ученые, которые пользуются графами как абстрактными единицами. Задача поиска маршрута в науке может быть и чисто фундаментальной, и прикладной.
- Дата-сайентисты. В этой области много математики, в том числе активно используется теория графов.
- Сетевые инженеры, так как алгоритм Дейкстры лежит в основе работы нескольких протоколов маршрутизации. Сама по себе компьютерная сеть представляет собой граф, поэтому специалисты по сетям должны знать, что это такое.
Профессия / 24 месяца
Data Scientist
Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.
Зачем нужен алгоритм Дейкстры
Основная задача — поиск кратчайшего пути по схеме, где множество точек соединено между собой отрезками. В виде такой схемы можно представить многие объекты реального мира, поэтому практических примеров использования алгоритма много:
- автоматическое построение маршрута на онлайн-карте;
- поиск системой бронирования наиболее быстрых или дешевых билетов, в том числе с возможными пересадками;
- моделирование движения робота, который перемещается по местности;
- разработка поведения неигровых персонажей, создание игрового ИИ в геймдеве;
- автоматическая обработка транспортных потоков;
- маршрутизация движения данных в компьютерной сети;
- расчет движения тока по электрическим цепям.
Станьте дата-сайентистом и решайте амбициозные задачи с помощью нейросетей
Как работает алгоритм
Алгоритм Дейкстры пошаговый. Сначала выбирается точка, от которой будут отсчитываться пути. Затем алгоритм поочередно ищет самые короткие маршруты из исходной точки в другие. Вершины, где он уже побывал, отмечает посещенными. Алгоритм использует посещенные вершины, когда рассчитывает пути для непосещенных.
Это может звучать сложно, поэтому мы хотим показать вам, как это выглядит на примере. Возьмем такой граф: цифрами в кружках обозначены вершины, а числа возле ребер — это вес путей между ними.
Инициализация. Пусть вершиной, из которой мы будем считать маршруты, будет 0. Расстояние до самой себя у этой вершины логично равно нулю. Остальные мы пока не знаем, поэтому отметим символом бесконечности.
Расстояние от 0 до 0 помечаем равным нулю, а саму вершину — посещенной.
Первый шаг алгоритма. Мы выбираем еще не посещенную вершину с самой маленькой меткой относительно исходной — то есть такую, которая находится ближе всех. На первом шаге это одна из соседних вершин — та, которая соединена с исходной самым «маленьким» ребром.
Для графа, который мы рассматриваем, это точка 2. Мы выбираем ее, «переходим» в нее и смотрим уже на ее соседей.
Дальнейшие шаги алгоритма. Для выбранной точки нужно осмотреть соседей и записать длину пути до них с учетом пройденного пути. А потом выбрать ближнюю точку. Но есть нюанс: нужно учитывать точки, которые мы уже использовали в прошлый раз. Если они дают более «выгодный» путь, лучше воспользоваться ими.
Например, на выбранном графе есть точка 1. В нее можно перейти из точки 2, где мы находимся. Но этот путь будет длиннее, чем при переходе напрямую из точки 0, а ведь она для нас исходная. Поэтому «короткий путь» для точки 1 — это маршрут 0–1. Отмечаем вершину посещенной.
Шаги повторяются, пока на графе есть непосещенные точки. Если вершину не посетили, она не участвует в расчетах. Если после ее «открытия» появился новый, более короткий путь к какой-либо точке, то минимальное расстояние для нее перезаписывается.
Конец алгоритма. Когда непосещенные вершины заканчиваются, алгоритм прекращает работу. Результат его действия — список кратчайших маршрутов до каждой точки из исходной. Для каждого маршрута указана его длина.
Мы говорим «длина», но это условно. Например, при поиске билетов в роли веса ребра может выступать их цена, а при организации электрической цепи — расход электроэнергии.
Теория графов — обширная отрасль дискретной математики. Ее используют во множестве сфер, от химии до разработки. В профильных университетах теорию графов изучают на курсе дискретной математики. Также получить базу знаний и решать практические задачи под контролем наставника можно на курсах SkillFactory.
Data Scientist
Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.
Статьи по теме:
Алгоритм Дейкстры нахождения кратчайшего пути
Рассмотрим пример нахождение кратчайшего пути. Дана сеть автомобильных дорог, соединяющих области города. Некоторые дороги односторонние. Найти кратчайшие пути от центра города до каждого города области.
Для решения указанной задачи можно использовать алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Работает только для графов без рёбер отрицательного веса.
Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.
Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.
Инициализация
Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Первый шаг
Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.
Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из 1-й во 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7.
Аналогично находим длины пути для всех других соседей (вершины 3 и 6).
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.
Второй шаг
Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.
Вершина 1 уже посещена. Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 < 17, поэтому метка не меняется. Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна 22 (7 + 15 = 22). Поскольку 22
Все соседи вершины 2 просмотрены, помечаем её как посещенную.
Третий шаг
Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим следующие результаты.
Четвертый шаг
Пятый шаг
Шестой шаг
Таким образом, кратчайшим путем из вершины 1 в вершину 5 будет путь через вершины 1 — 3 — 6 — 5, поскольку таким путем мы набираем минимальный вес, равный 20.
Займемся выводом кратчайшего пути. Мы знаем длину пути для каждой вершины, и теперь будем рассматривать вершины с конца. Рассматриваем конечную вершину (в данном случае — вершина 5), и для всех вершин, с которой она связана, находим длину пути, вычитая вес соответствующего ребра из длины пути конечной вершины.
Так, вершина 5 имеет длину пути 20. Она связана с вершинами 6 и 4.
Для вершины 6 получим вес 20 — 9 = 11 (совпал).
Для вершины 4 получим вес 20 — 6 = 14 (не совпал).
Если в результате мы получим значение, которое совпадает с длиной пути рассматриваемой вершины (в данном случае — вершина 6), то именно из нее был осуществлен переход в конечную вершину. Отмечаем эту вершину на искомом пути.
Далее определяем ребро, через которое мы попали в вершину 6. И так пока не дойдем до начала.
Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину.
Реализация алгоритма Дейкстры
Для хранения весов графа используется квадратная матрица. В заголовках строк и столбцов находятся вершины графа. А веса дуг графа размещаются во внутренних ячейках таблицы. Граф не содержит петель, поэтому на главной диагонали матрицы содержатся нулевые значения.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 7 | 9 | 0 | 0 | 14 |
| 2 | 7 | 0 | 10 | 15 | 0 | 0 |
| 3 | 9 | 10 | 0 | 11 | 0 | 2 |
| 4 | 0 | 15 | 11 | 0 | 6 | 0 |
| 5 | 0 | 0 | 0 | 6 | 0 | 9 |
| 6 | 14 | 0 | 2 | 0 | 9 | 0 |
Реализация на C++
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define SIZE 6
int main()
int a[SIZE][SIZE]; // матрица связей
int d[SIZE]; // минимальное расстояние
int v[SIZE]; // посещенные вершины
int temp, minindex, min;
int begin_index = 0;
system( «chcp 1251» );
system( «cls» );
// Инициализация матрицы связей
for ( int i = 0; i a[i][i] = 0;
for ( int j = i + 1; j
a[i][j] = temp;
a[j][i] = temp;
>
>
// Вывод матрицы связей
for ( int i = 0; i for ( int j = 0; j printf( «%5d » , a[i][j]);
printf( «\n» );
>
//Инициализация вершин и расстояний
for ( int i = 0; i d[i] = 10000;
v[i] = 1;
>
d[begin_index] = 0;
// Шаг алгоритма
do minindex = 10000;
min = 10000;
for ( int i = 0; i < // Если вершину ещё не обошли и вес меньше min
if ((v[i] == 1) && (d[i]
min = d[i];
minindex = i;
>
>
// Добавляем найденный минимальный вес
// к текущему весу вершины
// и сравниваем с текущим минимальным весом вершины
if (minindex != 10000)
for ( int i = 0; i if (a[minindex][i] > 0)
temp = min + a[minindex][i];
if (temp < d[i])
d[i] = temp;
>
>
>
v[minindex] = 0;
>
> while (minindex < 10000);
// Вывод кратчайших расстояний до вершин
printf( «\nКратчайшие расстояния до вершин: \n» );
for ( int i = 0; i printf( «%5d » , d[i]);
// Восстановление пути
int ver[SIZE]; // массив посещенных вершин
int end = 4; // индекс конечной вершины = 5 — 1
ver[0] = end + 1; // начальный элемент — конечная вершина
int k = 1; // индекс предыдущей вершины
int weight = d[end]; // вес конечной вершины
while (end != begin_index) // пока не дошли до начальной вершины
for ( int i = 0; i if (a[i][end] != 0) // если связь есть
int temp = weight — a[i][end]; // определяем вес пути из предыдущей вершины
if (temp == d[i]) // если вес совпал с рассчитанным
< // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
>
>
>
// Вывод пути (начальная вершина оказалась в конце массива из k элементов)
printf( «\nВывод кратчайшего пути\n» );
for ( int i = k — 1; i >= 0; i—)
printf( «%3d » , ver[i]);
getchar(); getchar();
return 0;
>
Результат выполнения
Комментариев к записи: 179
Алгоритм Дейкстры
В ориентированном взвешенном графе [math]G = (V, E)[/math] , вес рёбер которого неотрицателен и определяется весовой функцией [math]w : E \to \mathbb[/math] , алгоритм Дейкстры находит длины кратчайших путей из заданной вершины [math]s[/math] до всех остальных.
В алгоритме поддерживается множество вершин [math]U[/math] , для которых уже вычислены длины кратчайших путей до них из [math]s[/math] . На каждой итерации основного цикла выбирается вершина [math] u \notin U[/math] , которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина [math]u[/math] добавляется в множество [math]U[/math] и производится релаксация всех исходящих из неё рёбер.
Псевдокод
func dijkstra(s): for d[v] = used[v] = false d[s] = 0 for v = null for // найдём вершину с минимальным расстоянием if !used[j] and (v == null or d[j] < d[v]) v = j if d[v] == break used[v] = true for e : исходящие из v рёбра // произведём релаксацию по всем рёбрам, исходящим из v if d[v] + e.len < d[e.to] d[e.to] = d[v] + e.len
Обоснование корректности
Пусть [math]G = (V, E)[/math] — ориентированный взвешенный граф, вес рёбер которого неотрицателен, [math]s[/math] — стартовая вершина. Тогда после выполнения алгоритма Дейкстры [math]d(u) = \rho(s, u)[/math] для всех [math]u[/math] , где [math]\rho(s, u)[/math] — длина кратчайшего пути из вершины [math]s[/math] в вершину [math]u[/math]
Докажем по индукции, что в момент посещения любой вершины [math]u[/math] , [math]d(u) = \rho(s, u)[/math] .
Оценка сложности
В реализации алгоритма присутствует функция выбора вершины с минимальным значением [math]d[/math] и релаксация по всем рёбрам для данной вершины. Асимптотика работы зависит от реализации.
Пусть [math]n[/math] — количество вершин в графе, [math]m[/math] — количество рёбер в графе.
| Время работы | Описание | |||
|---|---|---|---|---|
| Поиск минимума | Релаксация | Общее | ||
| Наивная реализация | [math]O(n)[/math] | [math]O(1)[/math] | [math]O(n^2 + m)[/math] | [math]n[/math] раз осуществляем поиск вершины с минимальной величиной [math]d[/math] среди [math]O(n)[/math] непомеченных вершин и [math]m[/math] раз проводим релаксацию за [math]O(1)[/math] . Для плотных графов ( [math]m \approx n^2[/math] ) данная асимптотика является оптимальной. |
| Двоичная куча | [math]O(\log)[/math] | [math]O(\log)[/math] | [math]O(m\log)[/math] | Используя двоичную кучу можно выполнять операции извлечения минимума и обновления элемента за [math]O(\log)[/math] . Тогда время работы алгоритма Дейкстры составит [math]O(n\log + m\log) = O(m\log)[/math] . |
| Фибоначчиева куча | [math]O(\log)[/math] | [math]O(1)[/math] | [math]O(n\log + m)[/math] | Используя Фибоначчиевы кучи можно выполнять операции извлечения минимума за [math]O(\log)[/math] и обновления элемента за [math]O(1)[/math] . Таким образом, время работы алгоритма составит [math]O(n\log + m)[/math] . |
На практике удобно использовать стандартные контейнеры (например, std::set или std::priority_queue в C++).
При реализации необходимо хранить вершины, которые упорядочены по величине [math]d[/math] , для этого в контейнер можно помещать пару — расстояние-вершина. В результате будут храниться пары, упорядоченные по расстоянию.
Изначально поместим в контейнер стартовую вершину [math]s[/math] . Основной цикл будет выполняться, пока в контейнере есть хотя бы одна вершина. На каждой итерации извлекается вершина с наименьшим расстоянием [math]d[/math] и выполняются релаксации по рёбрам из неё. При выполнении успешной релаксации нужно удалить из контейнера вершину, до которой обновляем расстояние, а затем добавить её же, но с новым расстоянием.
В обычных кучах нет операции удаления произвольного элемента. При релаксации можно не удалять старые пары, в результате чего в куче может находиться одновременно несколько пар расстояние-вершина для одной вершины (с разными расстояниями). Для корректной работы при извлечении из кучи будем проверять расстояние: пары, в которых расстояние отлично от [math]d[v][/math] будем игнорировать. При этом асимптотика будет [math]O(m\log)[/math] вместо [math]O(m\log)[/math] .
Источники информации
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
- MAXimal :: algo :: Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры
- Википедия — Алгоритм Дейкстры
- Wikipedia — Dijkstra's algorithm
- Алгоритмы и структуры данных
- Кратчайшие пути в графах