最短增益路径法求解最大流问题

《最短增益路径法求解最大流问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、深圳大学实验报告课程名称:算法分析与复杂性理论实验项目名称:实验五最短增益路径法求解最大流问题学院:计算机与软件学院专业：软件工程指导教师:学号班级:实验时间：2015・10・22实验报告提交时间：2015U30教务部制•・实验目的1.掌握最短增益路径法思想。2.学会最大流问题求解方法。二.实验步骤与结果实验总体思路：通过capacity]][]二维数组存储对应边的容量，并用两个一维数组分别保存边的剩余流量和路径上当前节点的前驱。用C++中的queue类实现队列的相关操作，进而实现BFS算法。输入冇向图中边的个数和顶点个数Z后，通过一个for循

2、环获取对应边的始点、终点和容量，并将这些数据保存到capacity[][]数组屮。程序设计中将源点设为1,将汇点设为最后一个顶点。(代码和结果如下图所示)。各排序算法的实现及实验结果：1、EK算法代码1：boolEdmonds_Karp(intsrc,intdes,intn){intv,i；for(i=0;i

3、or(i=0;ique;pre[start]二0;que.push(start

4、);while(!que.empty()){v二que.front();que.pop();for(i=l;i<-n;++i){u=i;if(u==start

5、

6、pre[u]!=T

7、

8、map[v][u]==0)continue;pre[u]=v;flow[u]=MTN(flow[v],map[v][u]);que.push(u);}}if(flow[end]~maxint)returnT;returnflow[end];算法说明：每次用BFS找一条最短的增广路径，然后沿着这条路径修改流量值（实际修改的是残量网络的边权）。当没有增广路时，算法停止

9、，此时的流就是最大。实验结果:"C:UsersLaiDesktopM)^^^fi.exe1A—y.B、戈7IA4八一別1<<<<曰疋迭迭迭迭祐8次次次次烟61234-4,/5第第第啻取大大大大曰>>>販的的的一WUW!路（注：由于是根据前驱來找路径的，故输出路径为（终点，始点，容量）。）第1次迭代：（6,3,4）、（3,2,4）、（2,1,4）245第4次迭代：（6,3,2）、（3,2,2）、（2,1,2）厶、▲总结:根据通信网络中边的个数和顶点个数n=

10、V

11、,m=

12、E

13、,每进行一次增广BFS搜索算法，效率为0（m）,而在最坏的情况卜

14、•需耍（n-2）增广（即除源点和汇点外其他点都没有连通，所有点都只和s与t连通）。所以,最短增益路径法的时间复杂度为OWn）,这在稀疏图中效率比较高。四.实验心得解决一个问题最重要的是理解它的解题算法，只冇掌握解题的思路，才能使得程序的实现事半功倍。Edmonds-Karp算法实际上就是采用广度优先搜索來实现对增广路径的计算，这种算法思想在很多方面都有应用。实验过程难免会遇到问题，掌握好的调试技巧能够快速查找出问题的所在，并通过排查，逐一改正程序中存在的问题，不管用什么编译器，都耍学会设置适当的断点。遇到不懂的地方要多查看相关的书籍或者在网上查

15、找资料，这样才能真正学到东四。附件：源码#includettinclude#includeusingnamcspaccstd;ttdefinearraysize201intmaxData=0x7fffffff;intcapacity[arraysize][arraysize];intfl()w[arraysi7e];少流量可用intpre[arraysize];同时标记该节点是否在队列中intn,m;queuemyqueue;intBFS(intsrc,intdes){inti,j

16、;while(!myqueue.empty())myqueue.pop();for(i二1;i〈m+l;4"+i){preEi]=-l;}//记录残留