实验6 最短增益路径法求解最大流问题.docx

深圳大学实验报告课程名称:算法设计与分析实验项目名称：最短增益路求最大流问题学院：专业：指导教师：报告人：学号：班级：实验时间：2017年12月13日实验报告提交时间：2017年12月25日教务部制实验目的与要求：一、实验目的：(1) 掌握最短增益路径法思想。(2) 学会最大流问题求解方法。二、内容：1. 给定下面的通信网络，该网络中各节点之间的路径流量给定，使用最短增 益路径法求解该网络的最大流量，并进行流量分配。2. 要求用加权矩阵输入该网络，输出每次迭代过程中的最大流量及各路径分 配的流量。3. 如果能利用图形界面输出动态求解过程(在网络结构的图形显示中，标注 每一次求得的增益路径，并显示当前流量分配)，可获加分。三、算法思想提示1. 利用二维数组Ci,j和Fi,j分别存放容量和流量。2. 构建队列类Queue，该类具有取队首元素，加入队尾元素等方法。3. 具体算法过程参见教材pp.271-272四、实验要求1. 在blackboard提交电子版实验报告，注意实验报告的书写，整体排版。2. 实验报告的实验步骤部分需详细给出算法思想与实现代码之间的关系解 释，不可直接粘贴代码(直接粘贴代码者视为该部分内容缺失)。3. 实验报告样式可从http:/192.168.2.3/guide.aspx表格下载一学生适用一在校生管理一实践教学一实验：深圳大学学生实验报告）4. 源代码作为实验报告附件上传。5. 在实验课需要现场运行验证。方法、步骤：一. 实验思路：1.增广路径假如有一条路，这条路上的每一段都满足流量容量，我们一定能找到这 条路上的每一段的（容量-流量）的值当中的最小值。我们把这条路上每一段 的流量都加上，这条路就叫做增广路。我们通常记录容量而不记录流量，当 流量+ 的时候通过容量-来实现。不断地从起点开始寻找增广路，直到找 不到增广路为止。当前的流量就是最大流。图一：增广路径示意图2.反向边然而这样只能得到一个较优解，我们需要比较不同增广路的组合。即给程 序一个“后悔”的机会。在找到增广路之后，把每一段的容量减少的同时也 把反方向的容量增加。利用反向边把正向边已经用了的流量给“退”回去。3.基于层次图的优化一一Dinic首先对图进行一次BFS，然后在BFS生成的层次图中进行多次DFS。层次 图的意思就是，只有在BFS树中深度相差1的节点才是连接的。这就切断了原 有的图中的许多不必要的连接。图三：dinic算法二. 示意图：第1次迭代：(3, +3)(2, +2)第2次迭代:第3次迭代:(1,+3)(4, +4)第4次迭代:(2, +1) /Q(4,+4)(7 +1)3 +2):J 3/3 （4,+i）/树）经过了四次的迭代，可以看到，最大流为：3+2+1+4=10。三. 实验结果:表1当V= 300时，边数与时间的关系边数10000200003000040000500000时间/ms29.5775.26121.29223250.33表2当V= 300时，边数与时间的理论关系边数1000020000300004000050000时间/ms29.57118.28267.3473.12739.25表3当E= 4000时，顶点数与时间的关系顶点数100200003000040000500000时间/ms5.297.414.616.0619.45表4当E= 4000时，顶点数与时间的理论关系顶点数100200时间5.2910.630040050015.921.226.5绘制成折线图如下所示:最短增益路径法最短增益路径法600系列Y-系列2从图中看出，实际值与理论值相差较大，因为只是随机的一组数据，难以避免波动和偶然 性，下面对多组数据测时间，求平均值。SOU700600500400300200100001000020000 3OGDO 40000-5000060000v = sooHi边数与时间的关系100200300叫）时顶点数与时间的关系边数10000200003000040000500000时间12.2546.5195.45186.33303.366表5当V= 300时，边数与时间的关系边数1000020000300004000050000时间12.2549110.25196306.25表6当V= 300时，边数与时间的理论关系表7当E= 4000时，顶点数与时间的关系顶点数1002003004005000时间6.8812.1419.6826.2533.71表8当E= 4000时，顶点数与时间的理论关系顶点数10020030000400500时间6.8813.7620.6427.5234.4同样绘制成折线图，如下所示：I最短增益路径法350 300 -yk回财«L/I0 1(XXX 20WO 300004000050000v = 300 B1I边数与敖率之间的关系Y-条刊1 T-系列2结论：从图中可以发现，求平均的测试结果与理论值接近，避免了偶然误差，同时也证明 了理论的效率正确性。四. 总结：根据通信网络中边的个数和顶点个数n =|V| ,m = |E|,每进行一次增广 BFS搜索算法，效率为O(m),而在最坏的情况下需要(n-2)增广(即除源点和 汇点外其他点都没有连通，所有点都只和s与t连通)。所以，最短增益路径 法的时间复杂度为O(m*n)，这在稀疏图中效率比较高。五. 实验心得Edmonds-Karp算法实际上就是采用广度优先搜索来实现对增广路径的计 算，这种算法思想在很多方面都有应用。实验过程难免会遇到问题，掌握好的 调试技巧能够快速查找出问题的所在，并通过排查，逐一改正程序中存在的问 题，不管用什么编译器，都要学会设置适当的断点。遇到不懂的地方要多查看 相关的书籍或者在网上查找资料，这样才能真正学到东西。注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。