На этом шаге рассмотрим программную реализацию метода Форда-Фалкерсона.

    Неформально этот алгоритм может быть записан следующим образом:

   Формируем нулевой поток
   Пока существует путь из истока в сток, увеличивающий поток
      Выбираем Cmin - минимальную из остаточных пропускных способностей найденного пути
      Для каждой дуги (u,v) пути (из вершины u в вершину v)
         f[u,v] := f[u,v] + Cmin
         f[v,u] := -f[u,v]

    Далее приводится описание одного из вариантов программной реализации метода Форда-Фалкерсона.

Procedure MaxFlow;
var 
	KR, Cmin, u, v : integer; 
	path : array [0..MaxV] of integer; 
	i:integer;
begin
  Init; {Инициализация нулевого потока} 
  While ExistPath(KR,Cmin) do {CMin - минимальный из cf(u,v)=c(u,v)-f(u,v)} 
    for i:=KR downto 1 do {Для каждой дуги увеличивающего пути} 
    begin 
      u:= path[i+1]; {U->V - дуга с номером i в пути} 
      v:= path[i]; 
      f[u,v]:=f[u,v]+Cmin; {Увеличиваем поток на минимальную величину} 
      f[v,u]:=-f[u,v]; {f(v,u)=-f(u,v)} 
      cf[u,v]:=c[u,v]-f[u,v]; {Перевычисляем остаточную пропускную способность} 
      cf[v,u]:=c[v,u]-f[v,u]; {на дугах увеличивающего пути} 
    end; 
end;

    В процедуре MaxFlow вызываются процедура Init для инициализации нулевого потока и функция ExistPath, которая возвращает значение true, если увеличивающий путь существует, и значение false в противном случае.

    Очевидно, что если функция ExistPath возвращает значение false, то процедура MaxFlow завершает свою работу (увеличивающих путей больше нет).

    Если же ExistPath возвращает true (найден увеличивающий путь), то через свои параметры она возвращает также Cmin (минимальное значение из остаточных пропускных способностей дуг увеличивающего пути) и KR (количество дуг в увеличивающем пути).

    В глобальном для процедуры MaxFlow массиве path возвращаются номера вершин увеличивающего пути, перечисленные в порядке от стока к истоку.

    Если путь найден, то в соответствии с алгоритмом Форда-Фалкерсона для всех дуг увеличивающего пути пересчитывается поток f[u, v], строятся обратные дуги с отрицательным потоком f[v, u] и пересчитываются остаточные пропускные способности cf[u, v] и cf[v, u].

    На следующем шаге рассмотрим процедуру Init.

Предыдущий шаг Содержание Следующий шаг