用MATLAB求解最大流问题

function [f,wf,No]=MaxFlowMinCut_Me(n,C)

% 利用Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码

% f %显示最大流

% wf %显示最大流量

% No %显示标号, 由此可此芹悄得最小割

% n 节点个数

% C %弧容量

% Example:

% n=8

% C=[0 5 4 3 0 0 0 0

%0 0 0 0 5 3 0 0

%0 0 0 0 0 3 2 0

%0 0 0 0 0 0 2 0

%0 0 0 0 0 0 0 4

%0 0 0 0 0 0 0 3

%0 0 0 0 0 0 0 5

%0 0 0 0 0 0 0 0]

% [f,wf,No]=MaxFlowMinCut_Me(n,C)

for(i=1:n)for(j=1:n)f(i,j)=0endend %取初始可行流f 为零流

for(i=1:n)No(i)=0d(i)=0end %No,d 记录标号

while(1)

No(1)=n+1d(1)=Inf%给发点vs 标号

while(1)pd=1%标号过程

for(i=1:n)if(No(i)) %选择一个已标号的点vi

for(j=1:n)if(No(j)==0&f(i,j)<C(i,j)) %对于未给标号森渣的点vj, 当vivj 为首禅非饱和弧时

No(j)=id(j)=C(i,j)-f(i,j)pd=0

if(d(j)>d(i))d(j)=d(i)end

elseif(No(j)==0&f(j,i)>0) %对于未给标号的点vj, 当vjvi 为非零流弧时

No(j)=-id(j)=f(j,i)pd=0

if(d(j)>d(i))d(j)=d(i)endendendendend

if(No(n)|pd)breakendend %若收点vt 得到标号或者无法标号, 终止标号过程

if(pd)breakend %vt 未得到标号, f 已是最大流, 算法终止

dvt=d(n)t=n%进入调整过程, dvt 表示调整量

while(1)

if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt%前向弧调整

elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvtend %后向弧调整

if(No(t)==1)for(i=1:n)No(i)=0d(i)=0endbreakend %当t 的标号为vs 时, 终止调整过程

t=No(t)endend%继续调整前一段弧上的流f

wf=0for(j=1:n)wf=wf+f(1,j)end

end

在算法中一般存在最大-最小定理。

1

、最大匹配<==>最小覆盖

2、

最大流<==>最小割

最大流-最小割定理理解引自呆欧的形象表达：“多粗的管子，水就最多多大流量”，比如从自来水厂到用水大户工业小区A

能达到的水的最大流量是多大？考虑到可能从水厂到小区有不少到达的水管，那么最大的流量等于拆掉最少最细的水管后水厂不能给小区A

供水的那些水管流量的集合。当然这种说法并不不严谨，因为这里水管不是双向的，而在网络中谈论的信息流却可是是双向的。

其实最大流-最小割最难的地方在于构图了，还有必须掌握Dinic算法。

高效的求最大流算法——Dinci算法：

Dinci算法是基于“层次图”的时间效率优先的最大流算法。

层次：从源点走到终点的最短路长度。层次图：每次从源点到终点距离最短并且记录了多条增广路径（在找到最短路的过程记录了多条增广路径，因为找最短路径的过程中自然有分叉，有分叉那么祥举增广路径条数不就变多了么）。在dfs遍历的时候必须按照层次走。

Dinic算法的思想是为了减少增广次数，建立一个辅助网络L，L与原网络G具有相同的节点数，但边上的容量有所不同，在L上进行铅宴乱增广，将增广后的流值回写到原网络上，再建立当前网络的辅助网络，如此反复，达到最大流

Dinic三步曲：

1、利用原网络构造层次图，顺便判断原网络还有无增广路。

2、利用构造的层次图求此次的最大流，槐档若找不到增广路了则算法结束

3、更新原网络，即增广过程中遇见的边其正边以及逆边的的容量大小。

重复上述的三步。

---