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

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

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

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

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

Средняя последовательная сложность алгоритма на графах со случайными весами [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]