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

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

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

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

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

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

Входные данные:
  граф с вершинами 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'}

Последовательная сложность алгоритма

Средняя последовательная сложность алгоритма на графах со случайными весами [math]\displaystyle{ O(n + m + dL) }[/math], где [math]\displaystyle{ L }[/math] – максимальный суммарный вес кратчайшего пути, [math]\displaystyle{ d }[/math] – максимальная длина кратчайшего пути.

Ресурс параллелизма алгоритма

Средняя время работы параллельного алгоритма на графах со случайными весами на [math]\displaystyle{ O(n) }[/math] процессорах составляет [math]\displaystyle{ O((dL + \ln n) \ln n) }[/math] со средней работой [math]\displaystyle{ O(n + m + dL \ln n) }[/math]

Входные и выходные данные алгоритма

Входные данные: взвешенный граф [math]\displaystyle{ (V, E, W) }[/math] ([math]\displaystyle{ n }[/math] вершин [math]\displaystyle{ v_i }[/math] и [math]\displaystyle{ m }[/math] рёбер [math]\displaystyle{ e_j = (v^{(1)}_{j}, v^{(2)}_{j}) }[/math] с весами [math]\displaystyle{ f_j }[/math]), вершина-источник [math]\displaystyle{ u }[/math].

Объём входных данных: [math]\displaystyle{ O(m + n) }[/math].

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

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

Объём выходных данных: [math]\displaystyle{ O(n) }[/math].

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

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

• при [math]\displaystyle{ \Delta \to 0 }[/math]: алгоритм Дейкстры;
• при [math]\displaystyle{ \Delta \to \infty }[/math]: алгоритм Беллмана-Форда.

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

Существующие реализации алгоритма

• C++, MPI: Parallel Boost Graph Library (функция delta_stepping_shortest_paths).