Алгоритм Форда-Фалкерсона
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Форда-Фалкерсона[1] (с последующими усовершенствованиями Эдмондса-Карпа[2] и Е. А. Диница[3]) предназначен для решения задачи о максимальном потоке в транспортной сети. Время работы алгоритма [math]\displaystyle{ O(n^2m) }[/math] (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих [math]\displaystyle{ K }[/math], сложность [math]\displaystyle{ O(Km) }[/math].
Математическое описание
Вычислительное ядро алгоритма
Макроструктура алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Описание ресурса параллелизма алгоритма
Основной объём вычислений в алгоритме Форда-Фалкерсона приходится на поиск путей от источника к стоку. С этой целью может применяться поиск в ширину, который хорошо распараллеливается. Наилучших результатов можно достичь, если распределить вершины между узлами по слоям примерно одинаковой толщины, так что в каждом слое вершины были бы примерно на одинаковом удалении от источника (такое расслоение также можно найти поиском в ширину).
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- C++: Boost Graph Library (функция
edmonds_karp_max_flow): алгоритм Эдмонса–Карпа, сложность [math]\displaystyle{ O(nm^2) }[/math] для действительных весов и [math]\displaystyle{ O(Kmn) }[/math] для целых, не превосходящих [math]\displaystyle{ K }[/math]. - Python: NetworkX (функция
edmonds_karp): алгоритм Эдмонса–Карпа, сложность [math]\displaystyle{ O(nm^2) }[/math]. - Java: JGraphT (класс
EdmondsKarpMaximumFlow), алгоритм Эдмонса–Карпа, сложность [math]\displaystyle{ O(nm^2) }[/math].
Литература
- ↑ Ford, L R, Jr., and D R Fulkerson. “Maximal Flow Through a Network.” Canadian Journal of Mathematics 8 (1956): 399–404. doi:10.4153/CJM-1956-045-5.
- ↑ Edmonds, Jack, and Richard M Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM 19, no. 2 (April 1972): 248–64. doi:10.1145/321694.321699.
- ↑ Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.