zxfy_zdl.m

用Floyd算法设计的最小费用最大流

function myfun
clc,clear
M=1000000;
%原始费用矩阵
w=[0 4 1 M M
   M 0 M 6 1
   M 2 0 3 M
   M M M 0 2
   M M M M 0];
%原始容量矩阵
x=[M 10 8 0 0
   0 M 0 2 7 
   0 5 M 10 0
   0 0 0 M 4
   0 0 0 0 M];
v=w;  %费用矩阵
c=x;  %容量矩阵
m=size(w,2);
fl=zeros(m); %流量矩阵
while 1
    r=floyd(v,M); %求最短路
    if size(r,2)==0  %若没有最短路则退出
        break;
    end
    n=size(r,2);
    %求可能分配的最大流量
    k=M;
    for i=2:n
        if v(r(i-1),r(i))>0
            if k>c(r(i-1),r(i))-fl(r(i-1),r(i))
                k=c(r(i-1),r(i))-fl(r(i-1),r(i));
            end
        end
        if v(r(i-1),r(i))<0
            if k>fl(r(i),r(i-1))
                k=fl(r(i),r(i-1));
            end
        end
    end
    %调整流量
    for i=2:n
        if v(r(i-1),r(i))>0
            fl(r(i-1),r(i))=fl(r(i-1),r(i))+k;
        else
            fl(r(i),r(i-1))=fl(r(i),r(i-1))-k;
        end
    end
    %添加反向边，并删除正向饱和边
    for i=2:n
        v(r(i),r(i-1))=-v(r(i-1),r(i));
        c(r(i),r(i-1))=k;
        if v(r(i-1),r(i))>0
            if fl(r(i-1),r(i))==c(r(i-1),r(i))
                v(r(i-1),r(i))=M;
            end
        end
    end
end
fl
vf=0;
for i=2:m
    vf=vf+fl(1,i);
end
vf

%求最短路的Floyd算法
function r=floyd(b,M)
v=b;
n=size(b,2);
for k=1:n
   for i=1:n
      for j=1:n
         if b(i,j)>b(i,k)+b(k,j)
            b(i,j)=b(i,k)+b(k,j);
         end
      end
   end
end
r=[];
%判断是否存在最短路
if b(1,n)<M
    r=n;
    m=n;
    while 1
        if v(1,m)==b(1,m)
            break;
        end
        for i=1:n
            if b(1,i)+v(i,m)==b(1,m) & m~=i
                r=[i r];
                m=i;
                break;
            end
        end
    end
    r=[1 r];
end