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

Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех $u,v \in V$. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Алгоритм

Дан граф G(V,E) с пропускной способностью c(u,v) и потоком f(u,v) = 0 для ребер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков:

• $\ f(u,v) \leqslant c(u,v)$. Поток из u в v не превосходит пропускной способности.
• $\ f(u,v) = - f(v,u)$.
• $\ \sum_v f(u,v) = 0 \Longleftrightarrow f_{in}(u) = f_{out}(u)$ для всех узлов u, кроме s и t. Поток не изменяется при прохождении через узел.

Остаточная сеть G_f(V,E_f) — сеть с пропускной способностью c_f(u,v) = c(u,v) − f(u,v) и без потока.

Вход Граф $\,G$ с пропускной способностью $\,c$, источник $\,s$ и сток $\,t$
Выход Максимальный поток $\,f$ из $\,s$ в $\,t$

1. $f(u,v) \leftarrow 0$ для всех ребер $\,(u,v)$
2. Пока есть путь $\,p$ из $\,s$ в $\,t$ в $\,G_f$, такой что $\,c_f(u,v) > 0$ для всех ребер $(u,v) \in p$:
   1. Найти $\,c_f(p) = \min\{c_f(u,v) \;|\; (u,v) \in p\}$
   2. Для каждого ребра $(u,v) \in p$
      1. $f(u,v) \leftarrow f(u,v) + c_f(p)$
      2. $f(v,u) \leftarrow f(v,u) - c_f(p)$

Путь может быть найден, например, поиском в ширину (алгоритм Эдмондса-Карпа) или поиском в глубину в G_f(V,E_f).

Сложность

Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено O(E*f), где E — число вершин в графе, f — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за O(E) и увеличивает поток как минимум на 1.

Пример

Следующий пример показывает первые шаги алгоритма Форда-Фалкерсона в транспортной сети с четырьмя узлами, источником A и стоком D. Этот пример показывает худший случай. При использовании поиска в ширину алгоритму потребуется всего лишь 2 шага.

Путь	Пропускная способность	Результат
	Начальная транспортная сеть
A,B,C,D	min(cf(A,B),cf(B,C),cf(C,D)) = min(c(A,B) − f(A,B),c(B,C) − f(B,C),c(C,D) − f(C,D)) = min(1000 − 0,1 − 0,1000 − 0) = 1
A,C,B,D	min(cf(A,C),cf(C,B),cf(B,D)) = min(c(A,C) − f(A,C),c(C,B) − f(C,B),c(B,D) − f(B,D)) = min(1000 − 0,0 − ( − 1),1000 − 0) = 1
	После 1998 шагов …
	Конечная сеть

Cсылки

• Анимация
• Визуализатор алгоритма

Литература

• Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1