Алгоритм Дейкстры
Алгоритм Дейкстры (англ. Dijkstra’s algorithm) находит кратчайшие пути от заданной вершины $s$ до всех остальных в графе без ребер отрицательного веса.
Существует два основных варианта алгоритма, время работы которых составляет $O(n^2)$ и $O(m \log n)$, где $n$ — число вершин, а $m$ — число ребер.
#Основная идея
Заведём массив $d$, в котором для каждой вершины $v$ будем хранить текущую длину $d_v$ кратчайшего пути из $s$ в $v$. Изначально $d_s = 0$, а для всех остальных вершин расстояние равно бесконечности (или любому числу, которое заведомо больше максимально возможного расстояния).
Во время работы алгоритма мы будем постепенно обновлять этот массив, находя более оптимальные пути к вершинам и уменьшая расстояние до них. Когда мы узнаем, что найденный путь до какой-то вершины $v$ оптимальный, мы будем помечать эту вершину, поставив единицу ($a_v=1$) в специальном массиве $a$, изначально заполненном нулями.
Сам алгоритм состоит из $n$ итераций, на каждой из которых выбирается вершина $v$ с наименьшей величиной $d_v$ среди ещё не помеченных:
(Заметим, что на первой итерации выбрана будет стартовая вершина $s$.)
Выбранная вершина отмечается в массиве $a$, после чего из из вершины $v$ производятся релаксации: просматриваем все исходящие рёбра $(v,u)$ и для каждой такой вершины $u$ пытаемся улучшить значение $d_u$, выполнив присвоение
$$ d_u = \min (d_u, d_v + w) $$
где $w$ — длина ребра $(v, u)$.
![]()
Алгоритм Дейкстры [1] предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Дейкстры (с использованием фибоначчиевой кучи [2] ) выполняется за время [math]O(m + n \ln n)[/math] и является асимптотически быстрейшим из известных последовательных алгоритмов для данного класса задач.
1.2 Математическое описание алгоритма
Пусть задан граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math] и выделенной вершиной-источником [math]u[/math] . Обозначим через [math]d(v)[/math] кратчайшее расстояние от источника [math]u[/math] до вершины [math]v[/math] .
Пусть уже вычислены все расстояния, не превосходящие некоторого числа [math]r[/math] , то есть расстояния до вершин из множества [math]V_r = \< v \in V \mid d(v) \le r \>[/math] . Пусть
Тогда [math]d(w) = d(v) + f(e)[/math] , и [math]v[/math] лежит на кратчайшем пути от [math]u[/math] к [math]w[/math] .
Величины [math]d^+(w) = d(v) + f(e)[/math] , где [math]v \in V_r[/math] , [math]e = (v, w) \in E[/math] , называются предполагаемыми расстояниями и являются оценкой сверху для настоящих расстояний: [math]d(w) \le d^+(w)[/math] .
Алгоритм Дейкстры на каждом шаге находит вершину с наименьшим предполагаемым расстоянием, помечает её как посещённую и обновляет предполагаемые расстояния для всех концов рёбер, исходящих из неё.
1.3 Вычислительное ядро алгоритма
Основные вычисления связаны с операциями над очередью с приоритетом:
- извлечение минимального элемента ( delete_min );
- уменьшение приоритета элемента ( decrease_key ).
1.4 Макроструктура алгоритма
Входные данные: граф с вершинами V, рёбрами E с весами f(e); вершина-источник u. Выходные данные: расстояния d(v) до каждой вершины v ∈ V от вершины u. Q := new priority queue for each v ∈ V: if v = u then d(v) := 0 else d(v) := ∞ Q.insert(v, d(v)) while Q ≠ ∅: v := Q.delete_min() for each e = (v, w) ∈ E: if d(w) > d(v) + f(e): d(w) := d(v) + f(e) Q.decrease_key(w, d(w))
1.5 Схема реализации последовательного алгоритма
Конкретная реализация алгоритма Дейкстры определяется выбором используемого алгоритма очереди с приоритетом. В простейшем случае это может быть массив или список, поиск минимума в котором требует просмотра всех вершин. Более эффективным является использование кучи; наилучшую известную оценку сложности имеет вариант с использованием фибоначчиевой кучи [2] .
Возможен вариант реализации, когда вершины добавляются в очередь не на этапе инициализации, а в момент первого посещения.
1.6 Последовательная сложность алгоритма
Последовательная сложность алгоритма равна [math]O(C_1 m + C_2n)[/math] , где
- [math]C_1[/math] – количество операций уменьшения расстояния до вершины;
- [math]C_2[/math] – количество операций вычисления минимума.
Оригинальный алгоритм Дейкстры использовал в качестве внутренней структуры данных списки, для которых [math]C_1 = O(1)[/math] , [math]C_2 = O(n)[/math] , так что общая сложность составляла [math]O(n^2)[/math] .
При использовании фибоначчиевой кучи [2] время вычисления минимума сокращается до [math]C_2 = O(\ln n)[/math] , так что общая сложность равна [math]O(m + n \ln n)[/math] , что является асимптотически наилучшим известным результатом для данного класса задач.
1.7 Информационный граф
Приводится граф алгоритма для базовой реализации алгоритма Дейкстры на списках или массивах.
![]()
Рисунок 1. Граф алгоритма без отображения входных и выходных данных. n=3. Желтым цветом обозначены операции сравнения, зеленым — операции изменения меток вершин, синим — пометка вершины.
1.8 Ресурс параллелизма алгоритма
Алгоритм Дейкстры допускает эффективную параллелизацию [3] , среднее время работы [math]O(n^\ln n)[/math] с объёмом вычислений [math]O(n \ln n + m)[/math] .
Алгоритм Δ-шагания может рассматриваться как параллельная версия алгоритма Дейкстры.
1.9 Входные и выходные данные алгоритма
Входные данные: взвешенный граф [math](V, E, W)[/math] ( [math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^_, v^_)[/math] с весами [math]f_j[/math] ), вершина-источник [math]u[/math] .
Объём входных данных: [math]O(m + n)[/math] .
Выходные данные (возможные варианты):
- для каждой вершины [math]v[/math] исходного графа – последнее ребро [math]e^*_v = (w, v)[/math] , лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math] , или соответствующая вершина [math]w[/math] ;
- для каждой вершины [math]v[/math] исходного графа – суммарный вес [math]f^*(v)[/math] кратчайшего пути от вершины [math]u[/math] к [math]v[/math] .
Объём выходных данных: [math]O(n)[/math] .
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.
- ↑ 2,02,12,2 Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1987): 596–615. doi:10.1145/28869.28874.
- ↑ Crauser, A, K Mehlhorn, U Meyer, and P Sanders. “A Parallelization of Dijkstra’s Shortest Path Algorithm,” Proceedings of Mathematical Foundations of Computer Science / Lecture Notes in Computer Science, 1450:722–31, Berlin, Heidelberg: Springer, 1998. doi:10.1007/BFb0055823.
- Уровень алгоритма
- Статьи в работе
Алгоритм Дейкстры
![]()
Алгоритм Дейкстры [1] предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Дейкстры (с использованием фибоначчиевой кучи [2] ) выполняется за время [math]O(m + n \ln n)[/math] и является асимптотически быстрейшим из известных последовательных алгоритмов для данного класса задач.
1.2 Математическое описание алгоритма
Пусть задан граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math] и выделенной вершиной-источником [math]u[/math] . Обозначим через [math]d(v)[/math] кратчайшее расстояние от источника [math]u[/math] до вершины [math]v[/math] .
Пусть уже вычислены все расстояния, не превосходящие некоторого числа [math]r[/math] , то есть расстояния до вершин из множества [math]V_r = \< v \in V \mid d(v) \le r \>[/math] . Пусть
Тогда [math]d(w) = d(v) + f(e)[/math] , и [math]v[/math] лежит на кратчайшем пути от [math]u[/math] к [math]w[/math] .
Величины [math]d^+(w) = d(v) + f(e)[/math] , где [math]v \in V_r[/math] , [math]e = (v, w) \in E[/math] , называются предполагаемыми расстояниями и являются оценкой сверху для настоящих расстояний: [math]d(w) \le d^+(w)[/math] .
Алгоритм Дейкстры на каждом шаге находит вершину с наименьшим предполагаемым расстоянием, помечает её как посещённую и обновляет предполагаемые расстояния для всех концов рёбер, исходящих из неё.
1.3 Вычислительное ядро алгоритма
Основные вычисления связаны с операциями над очередью с приоритетом:
- извлечение минимального элемента ( delete_min );
- уменьшение приоритета элемента ( decrease_key ).
1.4 Макроструктура алгоритма
Входные данные: граф с вершинами V, рёбрами E с весами f(e); вершина-источник u. Выходные данные: расстояния d(v) до каждой вершины v ∈ V от вершины u. Q := new priority queue for each v ∈ V: if v = u then d(v) := 0 else d(v) := ∞ Q.insert(v, d(v)) while Q ≠ ∅: v := Q.delete_min() for each e = (v, w) ∈ E: if d(w) > d(v) + f(e): d(w) := d(v) + f(e) Q.decrease_key(w, d(w))
1.5 Схема реализации последовательного алгоритма
Конкретная реализация алгоритма Дейкстры определяется выбором используемого алгоритма очереди с приоритетом. В простейшем случае это может быть массив или список, поиск минимума в котором требует просмотра всех вершин. Более эффективным является использование кучи; наилучшую известную оценку сложности имеет вариант с использованием фибоначчиевой кучи [2] .
Возможен вариант реализации, когда вершины добавляются в очередь не на этапе инициализации, а в момент первого посещения.
1.6 Последовательная сложность алгоритма
Последовательная сложность алгоритма равна [math]O(C_1 m + C_2n)[/math] , где
- [math]C_1[/math] – количество операций уменьшения расстояния до вершины;
- [math]C_2[/math] – количество операций вычисления минимума.
Оригинальный алгоритм Дейкстры использовал в качестве внутренней структуры данных списки, для которых [math]C_1 = O(1)[/math] , [math]C_2 = O(n)[/math] , так что общая сложность составляла [math]O(n^2)[/math] .
При использовании фибоначчиевой кучи [2] время вычисления минимума сокращается до [math]C_2 = O(\ln n)[/math] , так что общая сложность равна [math]O(m + n \ln n)[/math] , что является асимптотически наилучшим известным результатом для данного класса задач.
1.7 Информационный граф
Приводится граф алгоритма для базовой реализации алгоритма Дейкстры на списках или массивах.
![]()
Рисунок 1. Граф алгоритма без отображения входных и выходных данных. n=3. Желтым цветом обозначены операции сравнения, зеленым — операции изменения меток вершин, синим — пометка вершины.
1.8 Ресурс параллелизма алгоритма
Алгоритм Дейкстры допускает эффективную параллелизацию [3] , среднее время работы [math]O(n^\ln n)[/math] с объёмом вычислений [math]O(n \ln n + m)[/math] .
Алгоритм Δ-шагания может рассматриваться как параллельная версия алгоритма Дейкстры.
1.9 Входные и выходные данные алгоритма
Входные данные: взвешенный граф [math](V, E, W)[/math] ( [math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^_, v^_)[/math] с весами [math]f_j[/math] ), вершина-источник [math]u[/math] .
Объём входных данных: [math]O(m + n)[/math] .
Выходные данные (возможные варианты):
- для каждой вершины [math]v[/math] исходного графа – последнее ребро [math]e^*_v = (w, v)[/math] , лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math] , или соответствующая вершина [math]w[/math] ;
- для каждой вершины [math]v[/math] исходного графа – суммарный вес [math]f^*(v)[/math] кратчайшего пути от вершины [math]u[/math] к [math]v[/math] .
Объём выходных данных: [math]O(n)[/math] .
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.
- ↑ 2,02,12,2 Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1987): 596–615. doi:10.1145/28869.28874.
- ↑ Crauser, A, K Mehlhorn, U Meyer, and P Sanders. “A Parallelization of Dijkstra’s Shortest Path Algorithm,” Proceedings of Mathematical Foundations of Computer Science / Lecture Notes in Computer Science, 1450:722–31, Berlin, Heidelberg: Springer, 1998. doi:10.1007/BFb0055823.
- Уровень алгоритма
- Статьи в работе