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

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

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

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

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

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

1.8 Описание ресурса параллелизма алгоритма

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