zuidaliu.m

最大流算法,注释清晰。最大流问题,是网络流理论研究的一个基本问题,求网络中一个可行流f*,使其流量v(f)达到最大, 这种流f称为最大流,这个问题称为(网络)最大流问题。最大流问题是一个特殊的线性规划问题,就是在容量网络中,寻找流量最大的可行流。 最大流问题可以建立如下形式的线性规划数学模型: 式中v(f)称为这个可行流的流量、发点的净输出量或收点的净输出量。∞一般用标号法寻求有向最大流比用求线性规划问题的一般方法要方便得多。 最大的标号算法还用于解决多发点多收点网络的最大问题,设容量网络G有若干个发点x1,x2,...,xm;若干收点y1,y2,...,yn,可以添加两个新点vs,vt,用