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

редактировать

для вычисления максимального потока в сети потоков (эквивалентно минимальный разрез)

метод Форда – Фулкерсона или алгоритм Форда – Фулкерсона (FFA ) - это жадный алгоритм, который вычисляет максимальный поток в потоковой сети . Иногда его называют «методом», а не «алгоритмом», поскольку подход к поиску дополнительных путей в остаточном графе не полностью определен или определен в нескольких реализациях с разным временем выполнения. Он был опубликован в 1956 г. Л. Р. Форд младший и Д. Р. Фулкерсон. Имя «Форд – Фулкерсон» часто также используется для алгоритма Эдмондса – Карпа, который является полностью определенной реализацией метода Форда – Фулкерсона.

Идея алгоритма заключается в следующем: пока существует путь от источника (начальный узел) до приемника (конечный узел), с доступной емкостью на всех ребрах пути, мы отправляем поток по одной из дорожек. Потом находим другой путь и так далее. Путь с доступной емкостью называется расширяющимся путем.

Содержание

1 Алгоритм
2 Сложность
3 Интегральный пример
4 Непрерывный пример
5 Реализация Edmonds на Python - Алгоритм Карпа
6 См. Также
7 Примечания
8 Ссылки
9 Внешние ссылки

Алгоритм

Пусть $G (V, E) {\ displaystyle G (V, E)}$ $G (V, E)$ быть графом, и для каждого ребра от u до v пусть $c (u, v) {\ displaystyle c (u, v)}$ $c (u, v)$ будет емкость и $f (u, v) {\ displaystyle f (u, v)}$ $f (u, v)$ быть потоком. Мы хотим найти максимальный поток от источника s до стока t. После каждого шага в алгоритме сохраняется следующее:

Ограничения емкости	$∀ (u, v) ∈ E: f (u, v) ≤ c (u, v) {\ displaystyle \ forall (u, v) \ in E: \ f (u, v) \ leq c (u, v)}$ ${\ displaystyle \ forall (u, v) \ in E: \ f (u, v) \ leq c (u, v)}$	Поток по ребру не может превышать его пропускную способность.
Косая симметрия	$∀ (u, v) ∈ E: f (u, v) = - f (v, u) {\ displaystyle \ forall (u, v) \ in E: \ f (u, v) = - f (v, u)}$ ${\ displaystyle \ forall (u, v) \ in E: \ f (u, v) = - f (v, u)}$	Чистый поток от u к v должен быть противоположен чистому потоку от v к u (см. пример).
Сохранение потока	$∀ u ∈ V: u ≠ s и u ≠ t ⇒ ∑ w ∈ V f (u, w) = 0 {\ displaystyle \ forall u \ in V: u \ neq s {\ text {and}} u \ neq t \ Rightarrow \ sum _ {w \ in V} f (u, w) = 0}$ $\ forall u \ в V: u \ neq s {\ text {и}} u \ neq t \ Rightarrow \ sum _ {w \ in V} f (u, w) = 0$	Чистый поток к узлу равен нулю, за исключением источника, который «производит» поток, и раковина, которая «потребляет» поток.
Значение (е)	$∑ (s, u) ∈ E f (s, u) = ∑ (v, t) ∈ E f (v, t) {\ displaystyle \ sum _ {(s, u) \ in E} f (s, u) = \ sum _ {(v, t) \ in E} f (v, t)}$ $\ sum _ {(s, u) \ in E} f (s, u) = \ sum _ {(v, t) \ in E} f (v, t)$	Поток, выходящий из s, должен быть равен потоку, прибывающему в t.

Это означает, что поток через сеть является допустимым потоком после каждого раунда в алгоритме. Мы определяем остаточную сеть $G f (V, E f) {\ displaystyle G_ {f} (V, E_ {f})}$ $G_{f}(V,E_{f})$ как сеть с пропускной способностью $cf (u, v) = c (u, v) - f (u, v) {\ displaystyle c_ {f} (u, v) = c (u, v) -f (u, v)}$ $c_ {f} (u, v) = c (u, v) -f (u, v)$ и нет потока. Обратите внимание, что может случиться так, что поток из v в u разрешен в остаточной сети, но запрещен в исходной сети: if $f (u, v)>0 {\ displaystyle f (u, v)>0}$ $f(u,v)>0$ и $c (v, u) = 0 {\ displaystyle c (v, u) = 0}$ $c (v, u) = 0$ , затем $cf (v, u) = c (v, u) - f (v, и) знак равно е (и, v)>0 {\ displaystyle c_ {f} (v, u) = c (v, u) -f (v, u) = f (u, v)>0}$ $c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0$ .

Алгоритм Форд – Фулкерсон

Входные данные Для сети

G = (V, E) {\ displaystyle G = (V, E)}

G = (V, E)

с пропускной способностью c, исходный узел s и узел приемника t

Выход Вычислить поток f от s до t максимального значения

$f (u, v) ← 0 {\ displaystyle f (u, v) \ leftarrow 0}$ $f (u, v) \ leftarrow 0$ для всех ребер $(u, v) {\ displaystyle (u, v)}$ $(u,v)$
Хотя есть путь p от s до t в G f { \ displaystyle G_ {f}}, так что cf (u, v)>0 {\ displaystyle c_ {f} (u, v)>0}для всех краев (u, v) ∈ p {\ displaystyle (u, v) \ in p}:
1. Найти $cf (p) = min {cf (u, v): (u, v) ∈ p} {\ displaystyle c_ {f } (p) = \ min \ {c_ {f} (u, v) :( u, v) \ in p \}}$ $c_ {f} (p) = \ min \ {c_ {f} (u, v) :( u, v) \ in p \}$
2. Для каждого ребра (u, v) ∈ p {\ displaystyle ( u, v) \ in p}
  1. $f (u, v) ← f (u, v) + cf (p) {\ displaystyle f (u, v) \ leftarrow f (u, v) + c_ {f } (p)}$ $f (u, v) \ leftarrow f (u, v) + c_ {f} (p)$ (Направить поток по пути)
  2. $f (v, u) ← f (v, u) - cf (p) {\ displaystyle f (v, u) \ leftarrow f (v, u) -c_ {f} (p)}$ $f (v, u) \ leftarrow f (v, u) -c_ { f} (p)$ (поток может быть «возвращен» позже)

«←» обозначает присвоение. Например, «наибольший ← элемент» означает, что значение наибольшего изменения значения элемента.
"return "завершает алгоритм и выводит следующее значение.

Путь на шаге 2 можно найти с помощью например, поиск в ширину (BFS) или поиск в глубину в $G f (V, E f) {\ displaystyle G_ {f} (V, E_ {f})}$ $G_{f}(V,E_{f})$ . Если вы используете первый, алгоритм называется Эдмондс – Карп.

. Если на шаге 2 больше нет путей, s не сможет достичь t в остаточной сети. Если S - это набор узлов, достижимых s в остаточной сети, то общая пропускная способность в исходной сети ребер от S до остальной части V равна, с одной стороны, общему потоку, который мы нашли от s до t, и, с другой стороны, служит верхней границей для всех таких потоков. Это доказывает, что найденный нами поток максимален. См. также Теорема о максимальном потоке и минимальном разрезе.

Если график $G (V, E) {\ displaystyle G (V, E)}$ $G (V, E)$ имеет несколько источников и приемников, мы действуем следующим образом: Предположим, что $T = {t ∣ t является раковиной} {\ displaystyle T = \ {t \ mid t {\ text {является раковиной}} \}}$ ${\ displaystyle T = \ {t \ mid t {\ text {является раковиной}} \}}$ и $S = {s ∣ s является источником} {\ displaystyle S = \ {s \ mid s {\ text {является источником}} \}}$ ${\ displaystyle S = \ {s \ mid s {\ text {is источник}} \}}$ . Добавьте новый источник $s ∗ {\ displaystyle s ^ {*}}$ $s^{*}$ с ребром $(s ∗, s) {\ displaystyle (s ^ {*}, s)}$ $(s ^ {*}, s)$ от $s ∗ {\ displaystyle s ^ {*}}$ $s^{*}$ до каждого узла $s ∈ S {\ displaystyle s \ in S}$ $s \ в S$ , с емкостью $c (s ∗, s) = ds (ds = ∑ (s, u) ∈ E c (s, u)) {\ displaystyle c (s ^ {*}, s) = d_ {s} \; (d_ {s} = \ sum _ {(s, u) \ in E} c (s, u))}$ $c (s ^ {*}, s) = d_ {s} \; (d_ {s} = \ sum _ {(s, u) \ in E} c (s, u))$ . И добавьте новую раковину $t ∗ {\ displaystyle t ^ {*}}$ $t ^ {*}$ с краем $(t, t ∗) {\ displaystyle (t, t ^ {*})}$ $(t,t^{*})$ от каждого узла $t ∈ T {\ displaystyle t \ in T}$ $t \ in T$ до $t ∗ {\ displaystyle t ^ {*}}$ $t ^ {*}$ , с емкостью $c (t, t ∗) = dt (dt = ∑ (v, t) ∈ E c (v, t)) {\ displaystyle c (t, t ^ {*}) = d_ {t } \; (d_ {t} = \ sum _ {(v, t) \ in E} c (v, t))}$ $c (t, t ^ {*}) = d_ {t} \; (d_ {t} = \ sum _ {(v, t) \ in E } c (v, t))$ . Затем примените алгоритм Форда – Фулкерсона.

Кроме того, если узел u имеет ограничение емкости $du {\ displaystyle d_ {u}}$ $d_ {u}$ , мы заменяем этот узел двумя узлами $uin, uout {\ displaystyle u _ {\ mathrm {in}}, u _ {\ mathrm {out}}}$ ${\ displaystyle u _ {\ mathrm {in}}, u _ {\ mathrm {out}}}$ и край $(uin, uout) {\ displaystyle (u _ {\ mathrm {in}}, u_ {\ mathrm {out}})}$ ${\ displaystyle (u _ {\ mathrm {in}}, u _ {\ mathrm {out}})}$ с емкостью $c (uin, uout) = du {\ displaystyle c (u _ {\ mathrm {in}}, u _ {\ mathrm {out} }) = d_ {u}}$ ${\ displaystyle c (u _ {\ mathrm {in}}, u _ {\ mathrm {out}}) = d_ {u}}$ . Затем примените алгоритм Форда – Фулкерсона.

Сложность

При добавлении пути увеличения потока к потоку, уже установленному на графике, максимальный поток будет достигнут, когда на графике больше нет путей увеличения потока. Однако нет уверенности в том, что эта ситуация когда-либо будет достигнута, поэтому лучшее, что можно гарантировать, - это то, что ответ будет правильным, если алгоритм завершится. В случае, если алгоритм работает вечно, поток может даже не сходиться к максимальному потоку. Однако такая ситуация возникает только при нерациональных значениях расхода. Когда емкости являются целыми числами, время выполнения Форда – Фулкерсона ограничено $O (E f) {\ displaystyle O (Ef)}$ $O (Ef)$ (см. нотация большого O ), где $E {\ displaystyle E}$ $E$ - количество ребер в графе, а $f {\ displaystyle f}$ $е$ - максимальный поток в графе. Это связано с тем, что каждый дополнительный путь можно найти за $O (E) {\ displaystyle O (E)}$ $O (E)$ времени и увеличивает поток на целое число не менее $1 {\ displaystyle 1}$ $1$ , с верхней границей $f {\ displaystyle f}$ $е$ .

Вариантом алгоритма Форда – Фулкерсона с гарантированным завершением и временем выполнения, не зависящим от максимального значения потока, является Алгоритм Эдмондса – Карпа, который выполняется за $O (VE 2) {\ displaystyle O (VE ^ {2})}$ $O (VE ^ {2})$ времени.

Интегральный пример

В следующем примере показаны первые шаги Форда – Фулкерсона в потоковой сети с 4 узлами, источником $A {\ displaystyle A}$ $A$ и раковина $D {\ displaystyle D}$ $D$ . Этот пример показывает наихудшее поведение алгоритма. На каждом этапе по сети передается только поток $1 {\ displaystyle 1}$ $1$ . Если бы вместо этого использовался поиск в ширину, потребовалось бы всего два шага.

Путь	Емкость	Результирующая потоковая сеть
Начальная потоковая сеть
$A, B, C, D {\ displaystyle A, B, C, D}$ $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, D) - е (C, D)) = мин (1000 - 0, 1 - 0, 1000 - 0) = 1 {\ displaystyle {\ begin {align} \ min (c_ { f} (A, B), c_ {f} (B, C), c_ {f} (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 \ конец {выровнен}}}$ ${\ displaystyle {\ begin {align} \ min (c_ {f} (A, B), c_ {f} (B, C), c_ {f} (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 \ end {align}}}$
$A, C, B, D {\ displaystyle A, C, B, D}$ $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)).) = мин (1000-0, 0 - (- 1), 1000-0) = 1 {\ displaystyle {\ begin {align} \ min (c_ {f} (A, C), c_ {f} (C, B), c_ {f} (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 \ end {выровнено}}}$ ${\ displaystyle {\ begin {align} \ min (c_ {f} (A, C), c_ {f} (C, B), c_ {f} (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 \ end {align}}}$
После 1998 года больше шагов...
Конечная сеть потока

Обратите внимание, как поток "отодвигается назад" "от $C {\ displaystyle C}$ $C$ до $B {\ displaystyle B}$ $B$ при нахождении пути $A, C, B, D {\ displaystyle A, C, B, D}$ $A, C, B, D$ .

Пример без завершения

Рассмотрим потоковую сеть, показанную справа, с источником $s {\ displaystyle s}$ $s$ , стоком $t {\ displaystyle t}$ $t$ , мощности ребер $e 1 {\ displaystyle e_ {1}}$ $e_ {1}$ , $e 2 {\ displaystyle e_ {2}}$ $e_ {2}$ и $е 3 {\ displaystyle e_ {3}}$ $e_ {3}$ соответственно $1 {\ displaystyle 1}$ $1$ , $r = (5–1) / 2 {\ displaystyle r = ({\ sqrt {5 }} - 1) / 2}$ $r = ({\ sqrt {5}} - 1) / 2$ и $1 {\ displaystyle 1}$ $1$ и пропускная способность всех других ребер некоторое целое число $M ≥ 2 {\ displaystyle M \ geq 2}$ $M \ geq 2$ . Константа $r {\ displaystyle r}$ $r$ была выбрана так, что $r 2 = 1 - r {\ displaystyle r ^ {2} = 1-r}$ $r ^ {2} = 1-r$ . Мы используем увеличивающие пути в соответствии со следующей таблицей, где $p 1 = {s, v 4, v 3, v 2, v 1, t} {\ displaystyle p_ {1} = \ {s, v_ {4}, v_ {3}, v_ {2}, v_ {1}, t \}}$ $p_ {1} = \ { s, v_ {4}, v_ {3}, v_ {2}, v_ {1}, t \}$ , $p 2 = {s, v 2, v 3, v 4, t} {\ displaystyle p_ {2} = \ { s, v_ {2}, v_ {3}, v_ {4}, t \}}$ $p_ {2} = \ {s, v_ {2}, v_ {3}, v_ {4}, t \}$ и $p 3 = {s, v 1, v 2, v 3, t} {\ displaystyle p_ {3} = \ {s, v_ {1}, v_ {2}, v_ {3}, t \}}$ $p_ {3} = \ {s, v_ {1}, v_ {2}, v_ {3}, t \}$ .

Шаг	Путь расширения	Отправленный поток	Остаточная емкость
Шаг	Путь расширения	Отправленный поток	$e 1 {\ displaystyle e_ {1}}$ $e_ {1}$	$e 2 {\ displaystyle e_ {2}}$ $e_ {2}$	$e 3 {\ displaystyle e_ {3}}$ $e_ {3}$
0			$r 0 = 1 {\ displaystyle r ^ {0} = 1}$ $r ^ {0} = 1$	$r {\ displaystyle r}$ $r$	$1 {\ displaystyle 1}$ $1$
1	${s, v 2, v 3, t} {\ displaystyle \ {s, v_ {2}, v_ {3}, t \}}$ $\ {s, v_ {2}, v_ {3}, t \}$	$1 {\ displaystyle 1}$ $1$	$r 0 {\ displaystyle r ^ {0}}$ $r ^ {0}$	$r 1 {\ displaystyle r ^ {1}}$ $r ^ {1}$	$0 {\ displaystyle 0}$ ${\ displaystyle 0}$
2	$p 1 {\ displaystyle p_ {1}}$ $p_ {1}$	$r 1 {\ displaystyle r ^ {1}}$ $r ^ {1}$	$r 2 {\ displaystyle r ^ {2}}$ $r ^ {2}$	$0 {\ displaystyle 0}$ ${\ displaystyle 0}$	$r 1 {\ displaystyle r ^ {1}}$ $r ^ {1}$
3	$p 2 {\ displaystyle p_ {2}}$ $p_ {2}$	$r 1 {\ displaystyle r ^ {1}}$ $r ^ {1}$	$р 2 {\ displaystyle r ^ {2}}$ $r ^ {2}$	$r 1 {\ displaystyle r ^ {1}}$ $r ^ {1}$	$0 {\ displaystyle 0}$ ${\ displaystyle 0}$
4	$p 1 {\ displaystyle p_ {1}}$ $p_ {1}$	$р 2 {\ displaystyle r ^ {2}}$ $r ^ {2}$	$0 {\ displaystyle 0}$ ${\ displaystyle 0}$	$r 3 {\ displaystyle r ^ {3}}$ $r^{3}$	$r 2 {\ displaystyle r ^ {2} }$ $r ^ {2}$
5	$п 3 {\ displaystyle p_ {3}}$ $p_ {3}$	$r 2 {\ displaystyle r ^ {2}}$ $r ^ {2}$	$r 2 {\ displaystyle r ^ {2}}$ $r ^ {2}$	$r 3 {\ displaystyle r ^ {3}}$ $r^{3}$	$0 {\ displaystyle 0}$ ${\ displaystyle 0}$

Обратите внимание, что после шага 1, а также после шага 5 остаточные мощности ребер $e 1 {\ displaystyle e_ {1}}$ $e_ {1}$ , $е 2 {\ displaystyle e_ {2}}$ $e_ {2}$ и $e 3 {\ displaystyle e_ {3}}$ $e_ {3}$ имеют форму $rn {\ displaystyle r ^ {n}}$ $r^{n}$ , $rn + 1 {\ displaystyle r ^ {n + 1}}$ $r ^ {n + 1}$ и $0 {\ displaystyle 0}$ ${\ displaystyle 0}$ , соответственно, для некоторых $N ∈ N {\ Displaystyle п \ в \ mathbb {N}}$ $n \ in \ mathbb {N}$ . Это означает, что мы можем использовать увеличивающие пути $p 1 {\ displaystyle p_ {1}}$ $p_ {1}$ , $p 2 {\ displaystyle p_ {2}}$ $p_ {2}$ , $p 1 {\ displaystyle p_ {1}}$ $p_ {1}$ и $p 3 {\ displaystyle p_ {3}}$ $p_ {3}$ бесконечно много раз, и остаточные мощности этих ребер всегда будут в одном и том же виде. Общий поток в сети после шага 5 равен $1 + 2 (r 1 + r 2) {\ displaystyle 1 + 2 (r ^ {1} + r ^ {2})}$ $1 + 2 (r ^ {1} + r ^ {2})$ . Если мы продолжим использовать дополняющие пути, как указано выше, общий поток сходится к $1 + 2 ∑ i = 1 ∞ ri = 3 + 2 r {\ displaystyle \ textstyle 1 + 2 \ sum _ {i = 1} ^ { \ infty} r ^ {i} = 3 + 2r}$ $\ textstyle 1 + 2 \ sum _ {i = 1} ^ {\ infty} r ^ {i} = 3 + 2r$ . Однако обратите внимание, что существует поток значений $2 M + 1 {\ displaystyle 2M + 1}$ $2M + 1$ , отправляя $M {\ displaystyle M}$ $M$ единиц поток вдоль $sv 1 t {\ displaystyle sv_ {1} t}$ ${\ displaystyle sv_ {1} t}$ , 1 единица потока вдоль $sv 2 v 3 t {\ displaystyle sv_ {2} v_ {3} t}$ ${\ displaystyle sv_ {2} v_ {3} t}$ и $M {\ displaystyle M}$ $M$ единиц потока вдоль $sv 4 t {\ displaystyle sv_ {4} t}$ ${\ displaystyle sv_ {4} t}$ . Следовательно, алгоритм никогда не завершается, и поток даже не сходится к максимальному потоку.

Другой пример без завершения, основанный на алгоритме Евклида, приведен Backman Huynh ( 2018), где также показано, что время работы алгоритма Форда-Фалкерсона в худшем случае в сети $G (V, E) {\ displaystyle G (V, E)}$ $G (V, E)$ в порядковых числах равно $ω Θ (| E |) {\ displaystyle \ omega ^ {\ Theta (| E |)}}$ ${\ displaystyle \ omega ^ {\ Theta (| E |)}}$ .

Реализация Python Эдмондса – Карпа алгоритм

импорт коллекций класс Graph (object): "" "Этот класс представляет ориентированный граф с использованием представления матрицы смежности." "" Def __init __ (self, graph): self.graph = graph # остаточный граф self.row = len (graph) def bfs (self, s, t, parent): "" "Возвращает истину, если существует путь от источника 's' к 't' в остаточном графе. Также заполняет родительский элемент для хранения пути." "" # Пометить все вершины как непосещенные посещенные = [False] * self.row # Создать очередь для BFS queue = collec tions.deque () # Пометить исходный узел как посещенный и поставить его в очередь queue.append (s)hibited [s] = True # Стандартный цикл BFS при очереди: u = queue.popleft () # Получить все смежные вершины удаленной вершины u # Если соседний объект не был посещен, отметьте его # посещенным и поставьте его в очередь для ind, val в enumerate (self.graph [u]): if (hibited [ind] == False) и (val>0): queue.append (ind) посещено [ind] = True parent [ind] = u # Если мы достигли приемника в BFS, начиная с источника, то возвращаем # true, иначе false return loaded [t] # Возвращает максимальный поток от s до t в данном графе def edmonds_karp (self, source,ink): # Этот массив заполняется BFS и хранит путь parent = [-1] * self.row max_flow = 0 # Первоначально нет потока # Увеличьте поток, пока есть - это путь от источника к приемнику, а self.bfs (источник, приемник, родитель): # Найти минимальную остаточную емкость ребер по # пути, заполненному BFS. Или мы можем сказать, что найти максимальный поток # по найденному пути. path_flow = float ("Inf") s = сток, в то время как s! = source: path_flow = min (path_flow, self.graph [parent [s]] [s]) s = parent [s] # Добавить поток пути к общему потоку max_flow + = path_flow # обновить остаточную пропускную способность ребер и обратных ребер # по пути v = сток, пока v! = source: u = parent [v] self.graph [u] [v] - = path_flow self.graph [v] [u] + = path_flow v = parent [v] return max_flow

См. также

Примечания

Ссылки

Кормен, Томас Х. ; Лейзерсон, Чарльз Э. ; Ривест, Рональд Л. ; Стейн, Клиффорд (2001). «Раздел 26.2: Метод Форда – Фулкерсона». Введение в алгоритмы (Второе изд.). MIT Press и McGraw – Hill. С. 651–664. ISBN 0-262-03293-7.
Джордж Т. Хейнеман; Гэри Поллис; Стэнли Селкоу (2008). «Глава 8: Алгоритмы сетевого потока». Об алгоритмах в двух словах. Орейлли Медиа. С. 226–250. ISBN 978-0-596-51624-6.
Джон Кляйнберг ; Ива Тардос (2006). «Глава 7: Расширение проблемы максимального потока». Разработка алгоритмов. Pearson Education. С. 378–384. ISBN 0-321-29535-8.
Сэмюэл Гутекунст (2009). ENGRI 1101. Корнельский университет.
Бакман, Спенсер; Хьюнь, Тони (2018). «Трансфинитный Форд – Фулкерсон на конечной сети». Вычислимость. 7 (4): 341–347. arXiv : 1504.04363. doi : 10.3233 / COM-180082.

Внешние ссылки

Носитель, связанный с алгоритмом Форда-Фалкерсона на Wikimedia Commons