算法分析与复杂性理论 实验报告 最大流问题

1、深 圳 大 学 实 验 报 告课程名称： 算法分析与复杂性理论 实验名称： 实验五 最短增益路径法求最大流问题 学院： 计算机与软件学院 专业： 软件工程 报告人： 文成 学号： 2150230509 班级： 学术型 同组人： 无 指导教师： 杨烜 实验时间： 2015/11/232015/11/30 实验报告提交时间： 2015/11/28 教务处制一 实验目的与实验内容实验目的：（1）掌握最短增益路径法思想。（2）学会最大流问题求解方法。实验内容：1. 给定下面的通信网络，该网络中各节点之间的路径流量给定，使用最短增益路径法求解该网络的最大流量，并进行流量分配。2.要求用加权矩阵输入该网络

2、，输出每次迭代过程中的最大流量及各路径分配的流量。3.如果能利用图形界面输出动态求解过程（在网络结构的图形显示中，标注每一次求得的增益路径，并显示当前流量分配），可获加分。算法思想提示：1.利用二维数组Ci,j和Fi,j分别存放容量和流量。2.构建队列类Queue，该类具有取队首元素，加入队尾元素等方法。3.具体算法过程参见教材pp.271-272二实验步骤最大流问题的问题描述：如上图。s是源点，t为汇点，每条边上数字的含义是边能够允许流过的最大流量。可以将边看成管道，3代表该管道每秒最多能通过3个单位的流量。最大流问题即是说，从s点到t点，最大允许流量是多少？最大流问题的算法思想：最短增益路

3、径法(先标记先扫描算法)：用两个记号来标记一个新的顶点第一个标记指出从源点到被标记顶点还能增加多少流量第二个标记指出另一个顶点的名字，可加上+或-来表示顶点时通过前向边还是后向边访问到的算法及其伪代码：Maxflow (G)/最短增量路径算法的实现/输入：网络G，具有一个源点1和一个汇点n，每条边（i，j）的容量都是正整数Uij/输出：最大流量x/对网络中的每条边（i，j），设xij=0/把源点标记为，-，再把源点加入到空队列Q中While not Empty(Q) doiFront(Q);Dequeue(Q)for 从i到j的每条边do/前向边if j 没有被标记rij uij - xiji

4、f rij 0Lj minLi,xji;用L，i-来标记jEnqueue(Q,j)If 汇点被标记了/沿着找到的增益路径进行增量jn/从汇点开始，用第二个标记反向移动while j!=i/没有到达源点if 顶点j的第二个标记是i+xijxij+Lnelse/顶点j的第二个标记是i-xjixji-Lnji；ii的第二个标记指出的顶点除了源点，擦去所有顶点的标记用源点对Q重新初始化return x/当前流量是最大的思路以及代码解释：（全部源代码见附件）先创建一个解决问题的类，命名为G。计算最大流作为这个类中的一个方法来实现。利用二维数组Mapi,j和Flowi,j分别存放容量和流量。添加头文件#i

5、nclude ，后面需要用到队列，需要该类的取队首元素，加入队尾元素等方法。class Gpublic:G();G(int n,int start,int end);void Edge(int a,int b,int flow); /顶点a和顶点b之间的流量void Maxflow(); /计算最大流private:int N; /顶点个数intStart; /源点intEnd, /汇点*Map, /网络容量*Flow, /通过流量*Rest, /剩余流量*Pre, /标记流向,正为前向,负为后向*Sign, /顶点是否标记,0为未标记,1为已标记*P; /过程变量,记录流量bool Sign

6、N(); /标记顶点int Min(int a,int b); /计算最小值void Update(); /更新网络;构造函数就先定义两个G:G() Pre=NULL; /不带参数的构造函数G:G(int n,int start,int end) /带三个参数的构造函数，顶点个数，源点和汇点初始化在类G中，实现了void Maxflow();方法，用来计算最大流，其中标记顶点的函数定义为bool SignN();bool G:SignN()/标记顶点Update();/更新queue que;/创建一个队列的对象que.push(Start);/把源点放进队列里面SignStart=1;/将源

7、点标记PStart=1000;PreStart=-1;/标记流向为后向while(!que.empty()/While not Empty(Q) doint head=que.front();/不断地取队首为headque.pop();for(int i=1;i0 & Signi=0)/如果从head出发到其它顶点，有剩余流量大于0，并且没有被标记Pi=Min(Phead,Restheadi);Prei=head;Signi=1;if(i=End) return true;/当扫描到汇点后返回que.push(i);for(i=1;i0 & Signi=0)/如果有顶点到head的流量大于0.

8、并且没有被标记Pi=Min(Phead,Flowihead);Prei=-head;Signi=1;if(i=End) return true;/当扫描到汇点后返回que.push(i); return false;void G:Maxflow()/计算最大流int maxflow=0;while(SignN()/迭代地去标记顶点maxflow=maxflow+PEnd;for(int i=End;i1;i=abs(Prei)if(Prei0)/流向为前向FlowPreii=FlowPreii+PEnd;if(Prei0)/流向为后向Flowiabs(Prei)=Flowiabs(Prei)-

9、PEnd;cout最大流:maxflow236，一条4的通路。此时流量为4此时流量为6。此时流量为8。此时流量为10下一次迭代之后，流量没有增长，那么结束。最后的结果应该是这样的。最大流量为10由最大流最小割定理可以验证。该图的最小割为(2,5) (3,6) (4,5)，最小割流量为2+4+4=10。因为网络中的最大流量值等于它最小割的容量，可以验证上图的正确性。后面，我也实现了用加权矩阵输入该网络，输出每次迭代过程中的最大流量及各路径分配的流量。四 实验心得在现实生活中，在实际的网络中，网络的结点和边都是有容量限制的. 很多情况下我们需要知道在一个有容量限制的网络中两个指定结点（分别称为源点和汇点）之间最多能传输多少流量，并确定达到这个最大流量的传输策略. 网络最大流问题（简称最大流问题）就是描述这个问题的数学模型.求解最大流的算法有不少，在此次实验中，我学习到了最短增益路径法，也明白了，最大流量值和最小割容量是相等的。本次实验挺有难度的，让我明白了最大流问题的算法，对迭代改进算法的认识也更加深刻了。这次实验