clear all
%圖論最小費用最大流問題程序
%最大流未知
%C為容量鄰接矩陣
C=[0 8 7 0 0 0;
   0 0 5 9 0 0;
   0 0 0 0 9 0;
   0 0 2 0 0 5;
   0 0 0 6 0 10;
   0 0 0 0 0 0];
%B為費用鄰接矩陣
B=[0 2 8 0 0 0;
   0 0 5 2 0 0;
   0 0 0 0 3 0;
   0 0 1 0 0 6;
   0 0 0 4 0 7;
   0 0 0 0 0 0];
n=6;%6個點
f=zeros(n,n);%初始流為0流
w=ones(n,n)*inf;%鄰接矩陣初始化

while 1
%求最小費用流
%確定費用鄰接矩陣
for i=1:6
for j=1:6
if i==j
w(i,j)=0;
end   
if C(i,j)>0 %如果存在(i,j)這條邊(路),再對w作出調整
if f(i,j)<C(i,j)
w(i,j)=B(i,j);
end
if f(i,j)==C(i,j)
w(i,j)=inf;
end
if f(i,j)>0
w(j,i)=-B(i,j);
end
if f(i,j)==0
w(j,i)=inf;
end
end
end
end

%使用Ford算法求最短路
[minroad,s]=Ford(w);

if minroad==inf%若不存在費用最短路,則已是最小費用最大流跳出循環
break;
end

%調整可行流
%記錄最短路
t=n;
R=[n]; 
while 1
R=[R,s(t)];
if s(t)==1%找到最短路的初始點時跳出循環
break;
end
t=s(t);
end
%統計R中點數
for i=1:n
if R(i)==1
break;
end
end
number=i;%number為點數

%調整過程
%確定調整量
for j=number-1:-1:1
if C(R(j+1),R(j))>0%如果是正向邊
r(j)=C(R(j+1),R(j))-f(R(j+1),R(j));
end
if C(R(j),R(j+1))>0%如果是負向邊
r(j)=f(R(j),R(j+1));
end
end
dvt=min(r);%確定調整量
%調整
for j=number-1:-1:1
if C(R(j+1),R(j))>0%如果是正向邊
f(R(j+1),R(j))=f(R(j+1),R(j))+dvt;
end
if C(R(j),R(j+1))>0%如果是負向邊
f(R(j),R(j+1))=f(R(j),R(j+1))-dvt;
end
end

end
f %顯示最小費用最大流

wf=0;
for i=1:n
wf=wf+f(1,i);
end
wf %顯示流量

zwf=0;
for i=1:n
for j=1:n
zwf=zwf+f(i,j)*B(i,j);
end
end
zwf %顯示費用