Для чего используют алгоритм дейкстры

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

В ориентированном взвешенном графе [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] и производится релаксация всех исходящих из неё рёбер.

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

Обоснование корректности [ править ]

Докажем по индукции, что в момент посещения любой вершины [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] .

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

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

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

1. 1. Как работает алгоритм Дейкстры
2. 2. Пример алгоритма Дейкстры
3. 3. Алгоритм Дейкстры. Псевдокод.
4. 4. Код для алгоритма Дейкстры

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

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

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

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

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

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

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

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

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

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

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

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

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