Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
Алгоритм Форда-Фалкерсона — алгоритм, решающий задачу нахождения максимального потока в транспортной сети.
Идея
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение обхода в глубину (dfs). Процесс повторяется, пока можно найти увеличивающий путь.
: для всех из . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника к стоку , вдоль которого можно послать ненулевой поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощьюРеализация
int dfs(int u, int Cmin): // Cmin — пропускная способность в текущем подпотоке
if u = t
return Cmin
visited[u] = true
for v in u.children
auto uv = edge(u, v)
if not visited[v] and uv.f < uv.c
int delta = dfs(v, min(Cmin, uv.c - uv.f))
if delta > 0
uv.f += delta
uv.backEdge.f -= delta
return delta
return 0
Оценка производительности
Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено
, где — число рёбер в графе, — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за и увеличивает поток как минимум на .
Пример несходящегося алгоритма
Рассмотрим приведённую справа сеть с источником
, стоком , пропускными способностями рёбер , и соответственно , и и пропускной способностью всех остальных рёбер, равной целому числу . Константа выбрана так, что . Мы используем пути из остаточного графа, приведённые в таблице, причём , и .Шаг | Найденный путь | Добавленный поток | Остаточные пропускные способности | ||
---|---|---|---|---|---|
Заметим, что после шага
, как и после шага , остаточные способности рёбер , и имеют форму , и , соответственно, для какого-то натурального . Это значит, что мы можем использовать увеличивающие пути , , и бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме. Полный поток после шага равен . За бесконечное время полный поток сойдётся к , тогда как максимальный поток равен . Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.Пример медленной работы алгоритма Форда-Фалкерсона с использованием поиска в глубину по сравнению с реализацией, использующей поиск в ширину
При использовании поиска в ширину алгоритму потребуется всего лишь два шага. Дана сеть (Рис. 2).
Благодаря двум итерациям (Рис. 3 и Рис. 4)
рёбра
насытились лишь на . Конечная сеть будет получена ещё через 1998 итераций (Рис. 5).См. также
Источники информации
- Википедия: Алгоритм Форда — Фалкерсона
- Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1