基于栈的网络最大流算法

《基于栈的网络最大流算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于栈的网络最大流算法厍向阳11(西安科技大学计算机科学与技术学院，西安，710054)1(xiangyangshe@sohu.com)摘收稿日期：_____________________；修回日期：____________________。基金项目：陕西省自然科学基金项目(2009JM7007)、陕西省教育厅专项科研计划项目(08JK354)。作者简介：厍向阳(1968-)，男，汉族，陕西周至人，博士后，副教授，从事数据挖掘与智能信息处理、人工智能与模式识别、复杂系统建模与优化等方面研究。要:针

2、对网络最大流问题，在割集定义和最大流-最小割定理基础上，以邻接矩阵为网络数据存储结构，利用栈作为数据组织形式，遍历网络中所有割集，最小容量的割集既为网络最大流。流量网络其余分支流量由网络结点流量平衡条件来求解。该算法具有：①开辟了一种求解流量网络最大流的新的方法，克服了割集和最大流-最小割定理仅仅具有理论价值、没有实用价值的局限性。②根据最小容量的割集可以方便确定决定网络最大流的关键分支，为扩展网络流量提供直接技术支持。算法测试表明：基于栈的网络最大流算法是完全可行和有效的。关键词:网络最大流；割集

3、；栈；最小容量割集中图分类号:TP393.3文献标识码1.引言网络最大流问题和它的对偶——最小割问题是一对经典组合优化问题，在许多工程领域和科学领域有重要的应用，是计算机科学和运筹学重要的内容[1][2]。最大流问题已经有40多年的研究历史，目前网络最大流问题主要有两类算法：①组合算法。按在剩余网络中推进流方式的不同，组合算法分为:增载轨算法和预流推进算法。增载轨算法有Ford和Fulkerson的标号算法[3]、Dinic的阻塞流算法[4]和Ahuja和Orlin的最短增载轨算法[5]等。预流推进

4、算法有Karzanov的阻塞流算法[5]、Goldberg和Tarjan的推进重标号算法[7]、Goldgerg和Rao的二分长度阻塞流算法[8]等。②线性规划算法。最大流问题是一个特殊的线性规划问题，利用其特殊性，可以得到比一般线性规划算法更有效的算法，如：网络单纯形法、网络内点法[9][10]。在网络最大流问题中，割集概念和最大流-最小割定理是各种网络最大流算法理论基础，具有重要的理论意义，然而仅此而已，对具体网络最大流算法没有实用价值。本文针对网络最大流问题，根据割集定义和最大流-最小割定理，

5、以邻接矩阵为网络数据存储结构，利用栈作为数据组织形式，遍历网络中所有割集，找到的最小容量的割集既为网络最大流。流量网络其余分支流量由网络结点流量平衡条件来求解。最后，通过实例进行了算法测试和比较。2.问题描述和预备知识2.1网络与流1.流网络在以为结点集，为弧集，且、为图G中结点和分支数，且=m、=n。有向图5上定义如下的权函数：为弧上的权函数，弧对应的权记为，称为弧的容量上界，或直接称为容量(Capacity)；依此构成的网络称为流网络，记为。2.可行流对于流网络，其上的一个流是指从的弧集的函数，

6、即每一条弧赋予一个流量。在流网络中指定一个源结点和一个汇结点，其余点为中转点。如果流网络中存在从到的流，且满足：（1）（2）则称为流网络中从到的可行流，流量记为。式（1）为弧的容量约束条件，式（2）为结点流量平衡条件。3.最大可行流在流网络的所有从到的可行流中，流量最大的可行流称为最大可行流，亦满足下式：（3）以式（3）作为目标函数，以式（1）、（2）为约束条件，便可构成网络最大流模型。2.2基本理论[11]1.割集容量网络，、分别为源点、汇点，若有边集，将分为两个子图和，其顶点集合分别为，，，，，

7、满足：①不连通；②，而连通。则称为的割集，记。2.割集容量割集中所有始点在，终点在的边的容量之和，称为割集的容量，记为3.最大流-最小割定理由割集定义不难看出，在容量网络中割集是由源点到汇点的必由之路，无论去掉那个割集，到便不相通。5可行流有界性定理：设为网络的任一可行流，流量为，是分离、的任意割集，则有。最大流-最小割定理：任一网络，从到的最大流的流量等于分离、的最小割集容量。3.基于栈的网络最大流搜索算法1.基本思想根据割集定义和最大流-最小割定理，以邻接矩阵为网络数据存储结构，利用栈作为数据组

8、织形式，采用深度搜索的方法来遍历网络中所有可能的割集[12]，按照网络割集的定义进行筛选，最后找到的容量最小的割集既为网络最大流量。2.基于栈的网络最大流搜索算法算法：基于栈的网络最大流搜索算法。输入：网络的流量的邻接矩阵。输出：最小割集、网络最大流流量。方法：Step1.设置，最小割集的初始割集，初始容量；Step2.源点进栈，栈顶位置Top=0，；Step3.判断是否满足割集的条件。若满足，则，并计算，转向Step4，否则，转向Step5。Step4.若，则，；S