Рассмотрим сеть G=(J, U) с одним источником S и одним стоком t и для всех дуг сети (i, j) заданы их пропускные способности C_ij. Найти величину максимального потока в сети, который можно направить из источника в сток и минимальный разрез в сети. Метод Форда – Фалкерсона называют еще и методом пометок. Рассмотрим его по шагам.

1 шаг: находим величину начального потока в сети. В качестве начального потока можно рассмотреть нулевой поток, положив значения всех X_ij=0. Однако, можно начинать и с конкретной величины потока. Величина V₀ начального потока в сети найдем следующим образом. Найдем в сети пути, не имеющие общих дуг и связывающие источник со стоком. Определим потоки, текущие по этим путям. Сумма этих потоков и определит начальное значение потока V_0.

2 шаг: пометим источник S меткой (). Первая цифра этой метки и означает, что мы идем из источника. Вторая цифра означает, что величина потока в источнике не ограничено большая. Рассмотрим все помеченные вершины i (в начале это одна вершина S) и определяет все не помеченные вершины j , которые связаны дугами с вершиной i . Тем вершинам j которые связаны дугой (i, j), поток по которой X_ij<C_ij, присвоим метку (i⁺, E_j), где Е_j = min(E_i, C_ij — X_ij), а тем вершинам j для которой X_ji>0, присвоим метку (i^—, E_j), где Е_j = min(E_i, X_ji). Затем переходим к помеченной вершине j , для которой аналогично определяем непомеченные вершины, связанные с вершиной j дугами, и все непомеченные вершины помечаем аналогично тому как мы помечали вершину j.

В результате 2-го шага нам либо удается пометить вершину t , т. е. сток, либо пометить сток нельзя. Если сток нельзя пометить то поток в сети явл. максимальным. Если вершина t оказалась помеченной, то поток в сети можно увеличить.

3 шаг: вершина t может иметь метку двух видов: либо (j⁺, E_t), либо (j^— ,E_t).Это означает, что поток в сети можно увеличить на E_t . Если метка вида (j⁺, E_t), то это означает, что поток по дуге (j, t) увеличим на E_t и новое значение потока , где X_jt – предыдущее значение потока на дуге (j, t). Если вершина t имеет метку (j^— ,E_t), то в этом случае поток по обратной дуге (t, j) уменьшится на E_t ; и .

И затем в каждом из этих случ. мы переходим к вершине j. Вершина j также может иметь метку двух видов: (i⁺, E_j) или (j^—, E_j).

Если метка вершины i (i⁺, E_j), то поток по прямой дуге (i, j) увеличивается на E_t , т. е. .

Если метка вида (i^—, E_j), то поток по обратной дуге (j, i) уменьшиться на E_t, т. е.

Затем переходим к вершине i. Так будем действовать до тех пор, пока не прийдем к источнику, т.е. к вершине S. Т. е. двигаясь вдоль помеченных вершин, мы выделяем некоторую цепь и на прямых дугах этой цепи увеличим поток на E_t, а на обратных – уменьшается на E_t. В результате этих действий новый поток в сети V₀= V₀+ E_t.

Затем мы стираем все пометки и с полученной велич. потока V₁ , обозначив , переходим ко 2 шагу. Процесс увеличения потока в сети прекращается тогда, когда веошина t, т. е. сток пометить нельзя. Это означает, что на всех прямых дугах, связанных со стоком t, велич. потока равна пропускной способности дуг, т. е. прямые дуги насыщены потоком. А на всех обратных дугах поток равен 0. Минимальный разрез определяют дуги (i, j), для которых вершина i явл. помеченной, а вершина j – непомеченной.