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

《算法分析与复杂性理论-实验报告-最大流问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、路径分配的流量。3. 如果能利用图形界面输出动态求解过程（在网络结构的图形显示中，标注每一次求得的增益路径，并显示当前流量分配），可获加分。算法思想提示：1.  利用二维数组C[i,j]和F[i,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中WhilenotEmpty(Q)doi←Front(Q);Dequeue(Q)for从i到j的

4、每条边do//前向边ifj没有被标记rij←uij-xijifrij>0Ljmin{Li,xji};用L，i-来标记jEnqueue(Q,j)If汇点被标记了//沿着找到的增益路径进行增量j←n//从汇点开始，用第二个标记反向移动whilej!=i//没有到达源点if顶点j的第二个标记是i+xij←xij+Lnelse//顶点j的第二个标记是i-xji←xji-Lnj←i；i←i的第二个标记指出的顶点除了源点，擦去所有顶点的标记用源点对Q重新初始化returnx//当前流量是最大的思路以及代码解释：（全部源代码见附件）先创建一个解决问题的类，命名为G。计算最

5、大流作为这个类中的一个方法来实现。利用二维数组Map[i,j]和Flow[i,j]分别存放容量和流量。添加头文件#include，后面需要用到队列，需要该类的取队首元素，加入队尾元素等方法。classG{public:G();G(intn,intstart,intend);voidEdge(inta,intb,intflow);//顶点a和顶点b之间的流量voidMaxflow();//计算最大流private:intN;//顶点个数intStart;//源点intEnd,//汇点**Map,//网络容量**Flow,//通过流量**Rest,

6、//剩余流量*Pre,//标记流向,正为前向,负为后向*Sign,//顶点是否标记,0为未标记,1为已标记*P;//过程变量,记录流量boolSignN();//标记顶点intMin(inta,intb);//计算最小值voidUpdate();//更新网络};构造函数就先定义两个G::G(){Pre=NULL;}//不带参数的构造函数G::G(intn,intstart,intend)//带三个参数的构造函数，顶点个数，源点和汇点{初始化}在类G中，实现了voidMaxflow();方法，用来计算最大流，其中标记顶点的函数定义为boolSignN();bo

7、olG::SignN()//标记顶点{Update();//更新queueque;//创建一个队列的对象que.push(Start);//把源点放进队列里面Sign[Start]=1;//将源点标记P[Start]=1000;Pre[Start]=-1;//标记流向为后向while(!que.empty())//WhilenotEmpty(Q)do{inthead=que.front();//不断地取队首为headque.pop();for(inti=1;i<=N;i++){//如果为标记顶点j是由j到i的有向边和遍历队列中的前面顶点i相连接的，

8、而且j具有大于0的未使用容量rij=uij-xij，