资源描述：
《高级算法课程--实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、一、程序运行指南1、程序介绍本程序为高级算法课程的实验程序，共完成了二分图的最大匹配算法、最大网络流的Dinic算法和欧几里德TSP问题的ESTPAPPROX近似算法三个题目。经过测试，程序可以编译运行通过。程序的编码语言为JAVA，开发工具为Eclipse。2、运行方法该程序为Applet应用程序，目前已经将其嵌入到网页中进行显示，可以直接点击Algorithm.html页面运行。如果提示有阻止的内容，请选择“允许”。打开成功后，即可看到实验程序的运行界面。用户可以在相应的算法演示区域输入想要测试的数据，如果信息无误，在底部
2、的结果区域会显示运行结果。如图所示：二、Dinic算法1、实验名称利用JAVA语言实现最大网络流的Dinic算法2、实验目的在一个给定的网络(G,s,t,c)中找到一个从s到t的最大网络流问题被称为最大流问题。Dinic算法就是一个找到最大流的算法，并且可以将时间复杂度减少到O(mn2)。在算法MPLA中，在计算层次图后，增广路径逐条找出。相反，Dinic算法将更有效地找出所有这些增广路径，这也正是改进了运行时间的原因。3、算法基本思想Dinic算法是基于“层次图”的时间效率优先的最大流算法。层次是指从源点走到终点的最短路径长
3、度。因此，从源点开始，在层次图中沿着边不管怎么走，经过的路径一定是终点在剩余图中的最短路径。在Dinic算法中，我们首先要判断有没有能到达终点的路径（即判断是否存在增广路径），在这个过程中我们就可以把层次图计算出来，然后沿着层次图一层一层地寻找增广路径。如果找到一条增广路径就进行增广（注意在沿着层次图寻找增广路径的时候使用栈的结构，把路径压进栈中）。增广完成后就继续寻找，如果找不到则退栈，并继续寻找下一层节点是否有与这个节点相连的，知道栈为空。如在算法MPLA中那样，Dinic方法被分成之多n个阶段，每一个阶段由寻找出层次图和
4、关于此层次图的阻塞流以及用阻塞流来增加当前流这样几部分组成。中间的while循环基本上是一个深度优先搜索，在那里找到增广路径用来增加流量。这里，p=s,…,u是一条至此为止找到的当前路径。在内层的while循环中有两个基本的运算，如果在当前路径的一端是u而不是t，并且u至少有一条边自u引出，比如说(u,v)，则向前运算就开始了。这个运算包括添加v到p，并让它成为p的当前端点。另一方面，假如u不是t，并且没有边从u引出，此时进行后退运算。这个运算只是相当于把u从p的一端拿掉，并在当前层次图L中移去所有和u邻接的边，因为不可能有任
5、何增广路径经过u。如果t已到达，或者搜索后退到s点并且从s出来的所有邻接边都已探究，则内层的while循环结束。如果到达t，这也就说明一条增广路径被找到了，跟随在内while循环后的步骤将根据这一路径执行增值。另一方面，如果已经到达s，并且所有从它引出的边已被删除，那么就没有增值发生，并且对当前层次图的处理已完成。4、算法伪代码算法1实现最大流的Dinic算法输入：网络(G,s,t,c)输出：G中的最大流1.for每条边(u,v)∈E2.f(u,v)←03.endfor4.初始化剩余图，设R=G5.查找R中的层次图L6.whi
6、let为L中的顶点7.u←s8.p←u9.whileoutdegree(s)>0{开始阶段}10.whileu≠tandoutdegree(s)>011.ifoutdegree(u)>0then{前进}12.设(u,v)为L中的一条边13.p←p,v1.u←v2.else{exit}3.删除u和L中所有的邻接边4.从p的末尾删除u5.将u设置为p中最后一个顶点6.endif7.endwhile8.ifu=tthen9.设△为p中的瓶颈容量，用△增值p中的当前流。在剩余图中和层次图中调整p的容量，删除饱和边。设u是p中从s可到达
7、的最后顶点，注意u可能是s。10.endif11.endwhile12.从当前剩余图R中重新计算层次图L13.endwhile5、算法核心代码(1)深度优先遍历算法privatestaticintmyDFS(inttempV,intmyFlow){intmyD=myFlow;if(tempV==nodeNum)returnmyFlow;for(inti=1;i<=nodeNum;i++){if(temp[tempV][i]>0&&data[tempV]+1==data[i]){intflow=myDFS(i,myMIN(myD
8、,temp[tempV][i]));temp[tempV][i]-=flow;temp[i][tempV]+=flow;myD-=flow;}}returnmyFlow-myD;}(2)广度优先遍历算法privatestaticbooleanmyBFS(){for(inti=
