Алгоритм Δ-шагания
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм дельта-шагания[1] (англ. Δ-Stepping) предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм изначально проектировался с целью эффективной параллелизации.
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
Псевдокод последовательного алгоритма:
Входные данные: граф с вершинами V, рёбрами E с весами W; вершина-источник u; параметр Δ > 0. Выходные данные: расстояния d(v) до каждой вершины v ∈ V от вершины u. procedure DeltaStepping(V, E, W, u, Δ): LightEdges := { e ∈ E | W(e) ≤ Δ } HeavyEdges := { e ∈ E | W(e) > Δ } for each v ∈ V do d(v) := ∞ Relax(u, 0) while any({ Buckets(i) ≠ ∅ }): Bucket := first({ Buckets(i) ≠ ∅ }) Deleted := ∅ while Bucket ≠ ∅: Requests := FindRequests(Bucket, LightEdges) Deleted := Deleted ∪ Bucket Bucket := ∅ RelaxAll(Requests) RelaxAll(FindRequests(Deleted, HeavyEdges)) procedure Relax(v, x): if x < d(v): OldBucket := B(⌊d(v) / Δ⌋) NewBucket := B(⌊x / Δ⌋) OldBucket := OldBucket \ {v} NewBucket := NewBucket ∪ {v} d(v) := x procedure RelaxAll(R): for each (v, x) ∈ R do Relax(v, x) function FindRequests(V', E'): return { (w, d(w) + W(v, w)) | v ∈ V' and (v, w) ∈ E'}
1.6 Последовательная сложность алгоритма
Средняя последовательная сложность алгоритма на графах со случайными весами O(n + m + dL), где L – максимальный суммарный вес кратчайшего пути, d – максимальная длина кратчайшего пути.
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Средняя время работы параллельного алгоритма на графах со случайными весами на O(n) процессорах составляет O((dL + \ln n) \ln n) со средней работой O(n + m + dL \ln n)
1.9 Входные и выходные данные алгоритма
Входные данные: взвешенный граф (V, E, W) (n вершин v_i и m рёбер e_j = (v^{(1)}_{j}, v^{(2)}_{j}) с весами f_j), вершина-источник u.
Объём входных данных: O(m + n).
Выходные данные (возможные варианты):
- для каждой вершины v исходного графа – последнее ребро e^*_v = (w, v), лежащее на кратчайшем пути от вершины u к v, или соответствующая вершина w;
- для каждой вершины v исходного графа – суммарный вес f^*(v) кратчайшего пути от от вершины u к v.
Объём выходных данных: O(n).
1.10 Свойства алгоритма
Предельные случаи алгоритма Δ-шагания:
- при \Delta \to 0: алгоритм Дейкстры;
- при \Delta \to \infty: алгоритм Беллмана-Форда.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.