"图论程序算法大全：最小费用最大流算法MATLAB实现"

最小费用最大流算法是一种图论算法，通过在网络流中找到最小费用的最大流量。该算法在 MATLAB 中的实现代码如下： ```matlab n=5; C=[0 15 16 0 0 0 0 0 13 14 0 11 0 17 0 0 0 0 0 8 0 0 0 0 0]; % 弧容量 b=[0 4 1 0 0 0 0 0 6 10 0 2 0 3 0 0 0 0 0 20 0 0 0 0 0]; % 弧上单位流量的费用 wf=0; wf0=Inf; % wf 表示最大流量, wf0 表示预定的流量值 for(i=1:n) for(j=1:n) f(i,j)=0; end end % 取初始可行流 f 为零流 while(1) for(i=1:n) for(j=1:n) if(j~=i) a(i,j)=Inf; end end end % 构造有向赋权图 for(i=1:n) for(j=1:n) if(C(i,j)>0) u(i,j)=b(i,j)-f(i,j); else u(i,j)=0; end end end % 计算每条边的单位费用和剩余容量 for(i=1:n) for(j=1:n) if(C(i,j)>0) if(u(i,j)<=0) c(i,j)=Inf; else c(i,j)=wf*u(i,j)/C(i,j)+a(i,j); end end end end % 计算每条边的单位费用和剩余容量 for(i=1:n) [cmin,imin]=min(c(i,:)); [cmin,jmin]=min(c(:,imin)); if(cmin>=0) break; end delta=min(u(i,imin),-f(i,jmin)); if(delta<=0) break; end f(i,imin)=f(i,imin)+delta; f(jmin,i)=f(jmin,i)-delta; wf=wf+delta*c(i,imin); for(j=1:n) if(C(imin,j)>0 && a(imin,j)<Inf) a(imin,j)=a(imin,j)+cmin; end if(C(jmin,j)>0 && a(jmin,j)<Inf) a(jmin,j)=a(jmin,j)+cmin; end end end if(wf>=wf0) break; end end disp(f); % 输出最小费用最大流 ``` 该算法主要通过不断地找到最小费用路径来更新最大流量，直到达到预定的流量值或者不能再增加流量为止。最终输出最小费用最大流。