Алгоритм Форда-Фалкерсона

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

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

Алгоритм Форда-Фалкерсона (с последующими усовершенствованиями Эдмондса-Карпа и Е. А. Диница) предназначен для решения задачи о максимальном потоке в транспортной сети. Время работы алгоритма [math]\displaystyle{ O(n^2m) }[/math] (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих [math]\displaystyle{ K }[/math], сложность [math]\displaystyle{ O(Km) }[/math] (для алгоритма Эдмондса–Карпа).

Алгоритм последовательно улучшает допустимый поток, находя так называемый дополняющий путь и увеличивая поток вдоль этого пути. Варианты алгоритма отличаются способом нахождения дополняющего пути.

• В исходном алгоритме Форда–Фалкерсона способ выбора дополняющего пути не уточнялся.
• В алгоритме Эдмондса-Карпа выбирается кратчайший дополняющий путь, для чего используется поиск в ширину на каждой итерации;
• В алгоритме Диница для выбора кратчайшего пути поддерживается «расслоение» графа, так что поиск в ширину выполняется значительно реже.

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

В статье Эдмондса–Карпа (теорема 1) доказано, что количество последовательно построенных кратчайших дополнительных путей не превосходит [math]\displaystyle{ m(n + 1)/2 = O(mn) }[/math]. Основными операциями алгоритма являются поиск в ширину сложностью [math]\displaystyle{ O(m) }[/math] и обновление потока вдоль дополняющего пути сложностью [math]\displaystyle{ O(n) }[/math].

В алгоритме Эдмондса–Карпа выполняются следующие операции:

• поиск в ширину и определение кратчайшего пути на каждой итерации, сложность [math]\displaystyle{ O(m + n) }[/math], общая сложность [math]\displaystyle{ O(m^2n) }[/math];
• обновление потока вдоль дополняющего пути, сложность [math]\displaystyle{ O(n) }[/math], общая сложность [math]\displaystyle{ O(n^2 m) }[/math].

Таким образом, общая сложность составляет [math]\displaystyle{ O(m^2n) }[/math].

В алгоритме Диница выполняются следующие операции:

• поиск кратчайшего пути и обновление потока вдоль дополняющего пути на каждой итерации, сложность [math]\displaystyle{ O(n) }[/math], общая сложность [math]\displaystyle{ O(mn^2) }[/math];
• обновление расслоения на каждой итерации, сложность [math]\displaystyle{ O(1) }[/math], общая сложность [math]\displaystyle{ O(mn) }[/math];
• поиск в ширину для построения нового расслоения, сложность [math]\displaystyle{ O(m) }[/math], число построений не более [math]\displaystyle{ n }[/math], общая сложность [math]\displaystyle{ O(mn) }[/math].

Таким образом, общая сложность составляет [math]\displaystyle{ O(mn^2) }[/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].