图论算法及其MATLAB实现全书+源代码

图论算法及其MATLAB实现（全书+源代码）

function [f wf zwf]=BGf（Cb）

% function [f wf zwf]=BGf（Cb）
% 计算给定图的最小费用最大流
% C;%弧容量
% b;%弧上单位流量的费用
% f 最小费用最大流矩阵，wf 最大流量 zwf 最小费用

n=size（C2）;
wf=0;wf0=Inf; %wf表示最大流量 wf0表示预定的流量值
f=zeros（nn）; %取初始可行流f 为零流
while（1）
      a=ones（nn）*inf;
      for（i=1:n）
           a（ii）=0;
      end%构造有向赋权图
      for（i=1:n）
          for（j=1:n）
              if（C（ij）>0&f（ij）==0）
                  a（ij）=b（ij）;
              elseif（C（ij）>0&f（ij）==C（ij））
                  a（ji）=-b（ij）;
              elseif（C（ij）>0）a（ij）=b（ij）;
                  a（ji）=-b（ij）;
              end
          end
      end
      for（i=2:n）
          p（i）=Inf;s（i）=i;
      end %用Ford 算法求最短路 赋初值
      for（k=1:n）
          pd=1; %求有向赋权图中vs 到vt 的最短路
          for（i=2:n）
              for（j=1:n）
                  if（p（i）>p（j）+a（ji））
                      p（i）=p（j）+a（ji）;s（i）=j;pd=0;
                  end
              end
          end
          if（pd）
              break;
          end
      end %求最短路的Ford 算法结束
      if（p（n）==Inf）
          break;
      end %不存在vs 到vt 的最短路 算法终止。 注意在求最小费用最大流时构造有向赋权图中不会含负权回路 所以不会出现k=n
    dvt=Inf;t=n; %进入调整过程 dvt 表示调整量
while（1） %计算调整量
      if（a（s（t）t）>0）
          dvtt=C（s（t）t）-f（s（t）t）; %前向弧调整量
      elseif（a（s（t）t）<0）
          dvtt=f（ts（t））;
      end %后向弧调整量
      if（dvt>dvtt）
          dvt=dvtt;
      end
      if（s（t）==1）
          break;
      end %当t 的标号为vs 时 终止计算调整量
      t=s（t）;
end %继续调整前一段弧上的流f
pd=0;
if（wf+dvt>=wf0）
    dvt=wf0-wf;pd=1;
end%如果最大流量大于或等于预定的流量值
t=n;
while（1） %调整过程
    if（a（s（t）t）>0）
        f（s（t）t）=f（s（t）t）+dvt; %前向弧调整
    elseif（a（s（t）t）<0）
        f（ts（t））=f（ts（t））-dvt;
    end %后向弧调整
    if（s（t）==1）
        break;
    end %当t 的标号为vs 时 终止调整过程
    t=s（t）;end
    if（pd）
        break;
    end%如果最大流量达到预定的流量值
    wf=0; 
    for（j=1:n）
        wf=wf+f（1j）;
    end
end %计算最大流量
zwf=0;
for（i=1:n）
    for（j=1:n）
        zwf=zwf+b（ij）*f（ij）;
    end
end%计算最小费用
f; %最小费用最大流

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2015-09-01 20:05  图论算法及其MATLAB实现（全书+源代码）\
     文件    25530730  2012-05-05 15:08  图论算法及其MATLAB实现（全书+源代码）\图论算法及其MATLAB实现.pdf
     目录           0  2015-09-01 20:39  图论算法及其MATLAB实现（全书+源代码）\源代码\
     文件        2320  2009-08-28 16:21  图论算法及其MATLAB实现（全书+源代码）\源代码\BGf.m
     文件         514  2009-09-12 21:30  图论算法及其MATLAB实现（全书+源代码）\源代码\boundnetf.m
     文件         704  2010-01-25 23:07  图论算法及其MATLAB实现（全书+源代码）\源代码\centgraf.m
     文件         738  2009-08-28 16:32  图论算法及其MATLAB实现（全书+源代码）\源代码\cn2shorf.m
     文件         661  2009-09-12 20:26  图论算法及其MATLAB实现（全书+源代码）\源代码\colorcodf.m
     文件         995  2009-08-28 16:34  图论算法及其MATLAB实现（全书+源代码）\源代码\concom.m
     文件        1924  2009-09-12 20:19  图论算法及其MATLAB实现（全书+源代码）\源代码\graphcodf.m
     文件         872  2010-05-07 23:01  图论算法及其MATLAB实现（全书+源代码）\源代码\incandadf.m
     文件        1039  2009-08-28 21:40  图论算法及其MATLAB实现（全书+源代码）\源代码\Krusf.m
     文件         858  2010-05-07 23:01  图论算法及其MATLAB实现（全书+源代码）\源代码\mattransf.m
     文件        1554  2009-08-28 21:20  图论算法及其MATLAB实现（全书+源代码）\源代码\Primf.m
     文件         367  2015-09-01 20:38  图论算法及其MATLAB实现（全书+源代码）\源代码\shortdf.m