"图论算法matlab实现：最小费用最大流算法PDF"

)A) %有弧由结点 i 指向结点 j cf(i,j)=C(i,j)-f(i,j);%得到余流容量 if(cf(i,j)>0)%有剩余容量 a(i,j)=b(i,j);%给有向边赋权 end end end [f,cf,af,pre] = graphminspantree(a);%使用最短路径算法改造成新网络 if(f==0)%已达最优解 if(wf0==Inf)%当未规定最小费用 break; end if(wf<wf0)%达到规定的最小费用 break; end else fmin=Inf;%寻找增广路径 j=n; i=pre(j); while(i>0) if(cf(i,j)<fmin) fmin=cf(i,j);%得到最小余流量 end j=i; i=pre(j); end j=n; i=pre(j); while(i>0)%增广路径f 改变 f(i,j)=f(i,j)+fmin; f(j,i)= - f(i,j); j=i; i=pre(j); end wf=wf+fmin*af; end end cf a %显示最终网络 af f wf%显示最小费用最大流 %程序使用示例 生成随机图n=5;C=[0 15 16 0 00 0 0 13 140 11 0 17 00 0 0 0 80 0 0 0 0]; b=[0 4 1 0 00 0 0 6 10 2 0 3 00 0 0 0 20 0 0 0 0]; 使用最小费用最大流代码 [流网络，费用]=mincostflow(C,b) %确定最优解 C= [0 16 0 0 00 13 0 00 14 0 11 17 00 0 80 0 0 0 00 20 0 0 0 0]; %显示网络流C=[0 000 0 00 0 0 14 0 0 0 00 0 0 17 0 80 0 0 0 0 14 0 0 11 20 0]; %显示最小费用f=[0 21 14 0 0 0 0 0 20 0 11 10 0 4 0 13 0 0 0 0 0]; %显示总费用 f 费用 B)背景：图论程序算法大全.pdf包含各种图论程序算法的具体实现，其中就包括了MATLAB实现最小费用最大流算法的程序代码。通过该算法可以在网络流问题中求解最优解。 　　　方法：代码首先定义了弧容量C和弧上单位流量的费用b，并且通过for循环构造了有向赋权图。然后利用图的最短路径算法改造成新网络，用来求解最小费用最大流。接着通过增广路径方法不断更新最小费用和最大流量，直至达到最优解为止。 　　　结果：最后显示了最终网络、最小费用最大流的结果，并给出了程序使用示例和最优解的确定。 　　　结论：通过该MATLAB实现的最小费用最大流算法，可以方便地求解网络流问题的最优解，对于解决相关问题具有一定的参考意义。