Методика нахождения максимального потока в графе по алгоритму Форда-Фалкерсона

Предварительный шаг.

Записываем пропускные способности дуг сети в таблицу размерности (n+1) x (n+1), где n+1 – количество вершин сети G(E,e). Если пропускная способность дуги (E_i, E_j) больше нуля, а симметричной ей дуги (E_j, E_i) равна нулю, то в клетку (i,j) заносим b_ij, а в клетку (j,i) – нуль; если b_ij=b_ji=0, то клетки (i,j) (j,i) не заполняем

1. Находим по таблице путь из E₀ в E_n с пропускной способностью больше нуля. Для этого столбец, соответствующий вершине E₀ помечаем знаком *. Отыскиваем в E₀ –й строке элементы b_0j>0 и столбцы, в которых они находятся, помечаем сверху номером просматриваемой строки (цифрой 0). В результате окажутся выделенными все дуги (E₀, E_j) с положительной пропускной способностью. Эти дуги могут служить первыми дугами пути из E₀ в E_n.

Далее просматриваем те строки, номера которых совпадают с номерами помеченных столбцов. В каждой такой строе, например E_i-й отыскиваем элементы b_ij больше нуля находящиеся в непомеченных столбцах, и помечаем эти столбцы номером просматриваемой сроки. Таким образом, окажутся выделенными дуги, которые могут служить вторыми дугами путей из E₀ в E_n

Продолжаем аналогичный просмотр строк, номера которых совпадают с номерами помеченных столбцов, до тех пор, пока:

a. либо не будет помечен столбец E_n (сток). Это означает, что удалось выделить путь с пропускной способностью больше нуля из E₀ в E_n. В этом случае искомый путь находим, используя пометки столбцов. Пусть последняя вершина пути E_n помечена номером k. По этой метке находим предшествующую вершину E_k (при просмотре E_k был помечен столбец E_n, и дуга (E_k, E_n) – последняя в искомом пути). Элемент b_kn>0, стоящий на пересечении E_k-й строки и E_n-го столбца, отмечаем знаком минус (получим b^-_kn), а симметричный ему элемент b_nk, находящийся на пересечении E_n –й строки и – E_k го столбца,- знаком плюс (получим b⁺_nk). Так как просматривалась E_k - я строка, то перед этим был помечен, например, номером r, E_k - й столбец. Поэтому двигаясь от элемента b⁺_nk по E_k-му столбцу до r -й строки (дуга (E_r, E_k) предшествует дуге (E_k, E_n)) и отмечаем b_rk знаком минус, b_kr – знаком плюс. Продолжаем этот процесс до тех пор, пока не придем к E₀ -й строке и не отметим знаком минус элемент этой строки и знаком плюс – симметричный ему элемент. Переходим к п. 2.

b. Либо нельзя будет пометить новые столбцы (в просматриваемых строках не окажется положительных элементов, расположенных в непомеченных столбцах). В этом случае отсутствует путь из E₀ в E_n, проходящий по дугам с положительной пропускной способностью и общий повторяющийся шаг законен

2. Находим пропускную способность q найденного пути m, т.е. максимальное количество вещества, которое можно переместить из E₀ в E_n по путиm в единицу времени. Пропускная способность пути равна наименьшей из пропускных способностей дуг, входящих в этот путь, т.е. .

3. Определяем остаточные пропускные способности дуг найденного пути и симметричных к ним. Для этого из элементов таблицы b^-_il вычитаем q, а к элементам b⁺_il прибавляем q. В результате выполнения этого действия получим новую таблицу, аналогичную исходной, но с измененными пропускными способностями. Перейти к п.1, который применяем до тех пор, пока не получим окончательную таблицу, в которой нет ни одного пути из E₀ в E_n с пропускной способностью больше нуля