Введение
Алгоритм для вычисления максимального потока в сети потоков (эквивалентно; минимальный разрез). Метод Форда — Фулкерсона или алгоритм Форда — Фулкерсона (FFA) — это жадный алгоритм, вычисляющий максимальный поток в сети потоков. Иногда его называют «методом», а не «алгоритмом», поскольку подход к поиску увеличивающих путей в остаточном графе не полностью определён или он задаётся в нескольких реализациях с разным временем работы. Он был опубликован в 1956 году Л. Р. Фордом-младшим и Д. Р. Фулкерсоном. Название «Форд — Фулкерсон» часто также используется для алгоритма Эдмондса — Карпа, который является полностью определённой реализацией метода Форда — Фулкерсона. Идея алгоритма заключается в следующем: пока существует путь от источника (начальной вершины) к стоку (конечной вершине), с доступной пропускной способностью на всех рёбрах этого пути, мы пропускаем поток по одному из таких путей. Затем мы находим другой путь и так далее. Путь с доступной пропускной способностью называется увеличивающим путём.
The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a fully defined implementation of the Ford–Fulkerson method. The idea behind the algorithm is as follows: as long as there is a path from the source (start node) to the sink (end node), with available capacity on all edges in the path, we send flow along one of the paths. Then we find another path, and so on. A path with available capacity is called an augmenting path.
Сложность
Добавляя путь увеличения потока к уже существующему потоку в графе, максимальный поток будет достигнут, когда больше не удастся найти ни одного пути увеличения потока. Однако нет гарантии, что эта ситуация когда-либо наступит, поэтому можно гарантировать лишь корректность ответа при завершении алгоритма. Если алгоритм работает бесконечно, поток может даже не сойтись к максимальному потоку. Но такая ситуация возникает только при иррациональных значениях потока. Если емкости целые числа, время работы алгоритма Форда — Фулкерсона ограничено (см. нотацию «большое О») величиной , где — количество ребер в графе, а — максимальный поток в графе. Это связано с тем, что каждый путь увеличения можно найти за время , и он увеличивает поток на целое число, по крайней мере , с верхней границей . Вариацией алгоритма Форда — Фулкерсона с гарантированным завершением и временем работы, не зависящим от значения максимального потока, является алгоритм Эдмондса — Карпа, который работает за время .
A variation of the Ford–Fulkerson algorithm with guaranteed termination and a runtime independent of the maximum flow value is the Edmonds–Karp algorithm, which runs in time.
Пример интеграла
На следующем примере показаны первые шаги алгоритма Форда — Фулкерсона в сети потоков с 4 узлами, с источником и стоком. Этот пример демонстрирует поведение алгоритма в наихудшем случае. На каждом шаге по сети пропускается поток величиной 1. Если бы вместо этого использовался поиск в ширину, потребовалось бы всего два шага. Путь Пропускная способность Результирующая сеть потоков Начальная сеть потоков После 1998 шагов Конечная сеть потоков.
Обратите внимание, как поток "возвращается" из в при поиске пути .