网络流——Ford-Fulkerson 算法

最大流算法

Ford-Fulkerson 算法是用于计算容量网络 < V,E,c,s,t> 的最大流的算法。该算法主要基于如下定理：

定理： 可行流 f 是最大流当且仅当不存在关于 f 的增广链。

Ford-Fulkerson 将不断寻找图中存在的增广链，并调整该链所包含边的流量 f(i,j)，使得网络的流量 v(f) 增加。当图中不再存在关于 f 的增广链时，f 即为最大流。

算法(Ford-Fulkerson)

• 输入：c\in\mathbb R^{n\times n}, 1\leqslant s,t\leqslant n
  其中 c(i,j) 为有向边 i\rightarrow j 的容量，s,t 是容量网络的起点和终点。
• 输出：f\in\mathbb R^{n\times n}
  其中 f 为最大流。

---

\mathrm{while(1)}

a. 寻找网络的增广链
b. 调整增广链上的流量

下面的问题是如何从给定的 c,f 中寻找增广链。

寻找增广链

寻找增广链的过程类似于在图中构造子树。于是，集合 T 用来存储正在检查的顶点，R 用来存储还未被检查过的顶点：

• T=\{s\},~R=V-\{s\}；
• 从 T 中取出一个顶点 i，然后将其在 R 中的邻接点加入 T，并记录相应的路径和流量；
• 如果 i 的邻接点集中包含终点 t，说明已经找到增广链，退出循环；
• 从 T 中删除 i，从 R 中删除 i 及其邻接点；
• 当 T\neq\phi 时，回到第二步；
• 如果结束循环时 T=\phi，说明没有找到增广链，f 就是最大流，结束程序。

调整增广链上的流量

• 将增广链上的 f(i,j) 全部加上 \delta。

代码实现(MATBALB)

function f = FordFulkerman( c,s,t )
n=length(c);
f=zeros(n); % 初始流
while(1) % 开始寻找增长链
    T=s;R=setdiff(1:n,s);
    l=zeros(1,n);delta=zeros(1,n);delta(s)=inf;
    while(~isempty(T))
        i=T(1); % 选取元素
        T(T==i)=[];R(R==i)=[]; % 删除元素
        J=R(f(i,R)<c(i,R)); % i->j
        T=union(T,J);
        l(J)=i;delta(J)=min(delta(i),c(i,J)-f(i,J)); % 更新l,delta
        if(find(J==t,1)) % 邻接集中包含t
            T=-1;break;
        end
        R=setdiff(R,J);
        J=R(f(R,i)>0); % j->i 
        T=union(T,J);
        l(J)=-i;delta(J)=min(delta(i),f(J,i)); % 更新l,delta
        if(find(J==t,1)) % 邻接集中包含t
            T=-1;break;
        end
        R=setdiff(R,J);
    end
    if(T==-1) % 存在增广链
        delta=delta(t); % 用于调整的值
        j=t;i=l(j); % 更新f
        while(i)
            if(i>0) % i->j
                f(i,j)=f(i,j)+delta;
            else % j->i
                i=-i;
                f(j,i)=f(j,i)+delta;
            end
            j=i;i=l(j);
        end
    else % 程序结束
        return;
    end
end
end

使用以下指令即可获得最大流 f 的流量：

v=sum(f(s,:))-sum(f(:,s))