Изменения

'''Алгоритм Форда-Фалкерсона''' — алгоритм, решающий задачу нахождения максимального [[Определение сети, потока #Определение потока | потока]] в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение <tex>0</tex>: <tex> f(u,v) = 0 </tex> для всех <tex> u, v </tex> из <tex> V </tex>. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника <tex>s </tex> к стоку <tex>t</tex>, вдоль которого можно послать ненулевой поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью [[Обход в глубину, цвета вершин|обхода в глубину (dfs)]]. Процесс повторяется, пока можно найти увеличивающий путь.

'''functionint''' dfs('''int''' u, '''int''' Cmin): <span style="color:Green">// Cmin {{---}} пропускная способность в текущем подпотоке</span> '''if''' (u = t)

visited[u.col ] = ''true'' '''for''' (v '''in''' u.children) '''auto''' uv = edge(u, v) '''if''' (!'''not''' visited[v.col) ] '''and''' (uv.f < uv.c) '''int ''' delta = dfs(v, '''min'''(Cmin, uv.c - uv.f)) '''if''' (delta > 0)

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