数学建模社区-数学中国

标题: 最大流——Ford-Fulkerson算法实现问题 [打印本页]

作者: zyz数模    时间: 2013-8-17 14:24
标题: 最大流——Ford-Fulkerson算法实现问题
本帖最后由 袁海亮 于 2013-8-17 15:50 编辑

最大流——Ford-Fulkerson算法实现
clear,tic
u=[0 8 0 7 0 0
    0 0 9 5 0 0
    0 0 0 2 0 5
    0 0 0 0 9 0
    0 0 6 0 0 10];
% u indicates capacity
f(1,2)=1;f(1,4)=1;f(2,4)=-1;f(2,3)=1;f(3,4)=0;f(3,6)=1;f(4,5)=0; f(5,6)=1;
% f indicates the current flow
n=length(u);list=[];maxf(n)=1;
while maxf(n)>0
    maxf=zeros(1,n);
    pred=zeros(1,n); % 对每个节点j,在该节点可能的增广路上的前一个节点pred(j)
    list=1;record=list;
    maxf(1)=inf; % 沿该可能的增广路到节点j为止可以增广的最大流maxf(j)
    %list是未检查邻接点的标号点,record是已标号点
    while (~isempty(list))&(maxf(n)==0)
        flag=list(1);list(1)=[];   
        label1= find(u(flag,:)-f(flag,:));
        label1=setdiff(label1,record);   
        list=union(list,label1);     
        pred(label1)=flag;     
        maxf(label1)=min(maxf(flag),u(flag,label1)-f(flag,label1));
        record=union(record,label1);
        label2=find(f(:,flag));
        label2=label2';
        label2=setdiff(label2,record);
        list=union(list,label2);
        pred(label2)=-flag;
        maxf(label2)=min(maxf(flag),f(label2,flag));
        record=union(record,label2);  
    end
    if maxf(n)>0   
        v2=n; v1=pred(v2);      
        while v2~=1        
            if v1>0
                f(v1,v2)=f(v1,v2)+maxf(n);
            else
                v1=abs(v1);           
                f(v2,v1)=f(v2,v1)-maxf(n);     
            end
            v2=v1; v1=pred(v2);
        end
    end
end
f
toc
这个程序是教材上给的,我把u和f的值改了,然后标红的地方原来写的是f(2,4)=1,运算结果为f =

     0     8     0     7     0     0
     0     0     5     3     0     0
     0     0     0     0     0     5
     0     0     0     0     9     0
     0     0     0     0     0    10
依据题意应该是错误的。
将其改为f(2,4)=-1,运算结果才为f =
     0     8     0     7     0     0
     0     0     5     2     0     0
     0     0     0     0     0     5
     0     0     0     0     9     0
     0     0     0     0     0    10

求各位能不能帮忙看看是哪里出了问题,十分感谢。



作者: 冰E柠檬    时间: 2013-8-18 09:42
  你原文的题意是什么呢?
给你一个  最大流通用程序,你参考一下吧!

最大流通用程序.m

1.68 KB, 下载次数: 21, 下载积分: 体力 -2 点


作者: 飘逸    时间: 2013-8-20 12:52

作者: 沪上妖瞳    时间: 2015-9-2 15:21
啦啦啦啦·



作者: agathahe    时间: 2020-9-22 11:45
求教材,那本书上的?





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5