Уровень алгоритма

Алгоритм Δ-шагания

Материал из Алговики
Перейти к навигации Перейти к поиску
Get Perf.Data


1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм дельта-шагания[1] (англ. Δ-Stepping) предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм изначально проектировался с целью эффективной параллелизации.

1.2 Математическое описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

Псевдокод последовательного алгоритма:

Входные данные:
  граф с вершинами V, рёбрами E с весами W;
  вершина-источник u;
  параметр Δ > 0.
Выходные данные: расстояния d(v) до каждой вершины vV от вершины u.

procedure DeltaStepping(V, E, W, u, Δ):
     LightEdges := { e ∈ E | W(e) ≤ Δ }
     HeavyEdges := { e ∈ E | W(e) > Δ }
     for each vV do d(v) := ∞
     Relax(u, 0)
     while any({ Buckets(i) ≠ ∅ }):
         Bucket := first({ Buckets(i) ≠ ∅ })
         Deleted := ∅
         while Bucket ≠ ∅:
             Requests := FindRequests(Bucket, LightEdges)
             Deleted := DeletedBucket
             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)) | vV' 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).

Выходные данные (возможные варианты):

  1. для каждой вершины v исходного графа – последнее ребро e^*_v = (w, v), лежащее на кратчайшем пути от вершины u к v, или соответствующая вершина w;
  2. для каждой вершины v исходного графа – суммарный вес f^*(v) кратчайшего пути от от вершины u к v.

Объём выходных данных: O(n).

1.10 Свойства алгоритма

Предельные случаи алгоритма Δ-шагания:

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Возможные способы и особенности параллельной реализации алгоритма

2.3 Результаты прогонов

2.4 Выводы для классов архитектур

3 Литература

  1. 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.