最大流算法
Ford-Fulkerson 算法是用于計(jì)算容量網(wǎng)絡(luò) < V,E,c,s,t> 的最大流的算法霜定。該算法主要基于如下定理：
定理： 可行流 f 是最大流當(dāng)且僅當(dāng)不存在關(guān)于 f 的增廣鏈界弧。
Ford-Fulkerson 將不斷尋找圖中存在的增廣鏈沸停，并調(diào)整該鏈所包含邊的流量 f(i,j)愕乎，使得網(wǎng)絡(luò)的流量 v(f) 增加荧止。當(dāng)圖中不再存在關(guān)于 f 的增廣鏈時(shí)垮抗，f 即為最大流陆盘。
算法(Ford-Fulkerson)
- 輸入：c\in\mathbb R^{n\times n}, 1\leqslant s,t\leqslant n
其中 c(i,j) 為有向邊 i\rightarrow j 的容量，s,t 是容量網(wǎng)絡(luò)的起點(diǎn)和終點(diǎn)恤磷。- 輸出：f\in\mathbb R^{n\times n}
其中 f 為最大流面哼。
\mathrm{while(1)}
a. 尋找網(wǎng)絡(luò)的增廣鏈
b. 調(diào)整增廣鏈上的流量
下面的問題是如何從給定的 c,f 中尋找增廣鏈。
尋找增廣鏈
尋找增廣鏈的過程類似于在圖中構(gòu)造子樹扫步。于是魔策，集合 T 用來存儲(chǔ)正在檢查的頂點(diǎn)，R 用來存儲(chǔ)還未被檢查過的頂點(diǎn)：
- T=\{s\},~R=V-\{s\}河胎；
- 從 T 中取出一個(gè)頂點(diǎn) i闯袒，然后將其在 R 中的鄰接點(diǎn)加入 T，并記錄相應(yīng)的路徑和流量游岳；
- 如果 i 的鄰接點(diǎn)集中包含終點(diǎn) t政敢，說明已經(jīng)找到增廣鏈，退出循環(huán)胚迫；
- 從 T 中刪除 i喷户，從 R 中刪除 i 及其鄰接點(diǎn)；
- 當(dāng) T\neq\phi 時(shí)访锻，回到第二步褪尝；
- 如果結(jié)束循環(huán)時(shí) T=\phi，說明沒有找到增廣鏈朗若，f 就是最大流恼五，結(jié)束程序。
調(diào)整增廣鏈上的流量
- 將增廣鏈上的 f(i,j) 全部加上 \delta哭懈。
代碼實(shí)現(xiàn)(MATBALB)
function f = FordFulkerman( c,s,t )
n=length(c);
f=zeros(n); % 初始流
while(1) % 開始尋找增長(zhǎng)鏈
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); % 用于調(diào)整的值
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 % 程序結(jié)束
return;
end
end
end
使用以下指令即可獲得最大流 f 的流量：
v=sum(f(s,:))-sum(f(:,s))
