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

1、算法设计与分析实验四 最短增益路径法求解最大流问题问题一 问题 对于给定的通信网络，该网络中各节点之间的路径流量给定，如何求解该网络的最大流量，并进行流量分配？图的生成V = 4 E = 51s234t三 最大流最小割 设f是源点为s，汇点为t的流网络G中的流。并且(S,T)是G的一个割。则通过割(S,T)的净流为f(S,T)=|f|。证明: 由流守恒性得:f(S-s,V)=0 f(S,T)=f(S,V)-f(S,S)=f(s,V)=|f|任意割的净流都是相等的对于流网络G中任意流f，其值的上界为G的任意割的容量证明:设(S,T)为G中的任意割，f为任意流最大流的值不能大于最小割的容量（最大流

2、的值就是最小割的容量）|( , )( , )( , )( , )u S v Tu S v Tff S Tf u vc u vc S T二 最短增益路径法 1s24356t7 76 62 24 43 34 44 48 8(7,+1)(6,+1)(3,+2)(2,+2)(3,+3)3/43/43/33/33/73/7 1s24356t3/73/76 62 24 43/33/34 43/43/48 8(4,+1)(6,+1)(2,+2)(4,+4)(2,+5)2 2/8/82/22/25 5/7/7二 最短增益路径法 1s24356t5 5/7/76 62/22/24 43/33/34 43/43/

3、42/82/8(2,+1)(6,+1)(4,+4)(4,+4)(1,+3)4/44/41 1/4/41 1/6/6二 最短增益路径法 1s24356t5 5/7/71/61/62/22/21/41/43/33/34 44 4/4/42/82/8(2,+1)(5,+1)(3,+4)(4,+4)(4,+5)6 6/8/84 4/4/45 5/6/6最大流为10二 最短增益路径法 算法的效率为O(V*E2)三 最大流最小割 1s42356t7 76 62 24 43 34 44 48 81310 从包含源点的集合到包含汇点的集合的出度的最小值，即为最小割，也为最大流。三 最大流最小割开始顶点求解顶点

4、求解求解求解001101 用树的深度遍历将所有顶点分为两个集合，其中一个集合包含源点，另外一个集合包含汇点，然后求出从包含源点的集合到包含汇点的集合的出度的最小值，即为最小割，也为最大流。将顶点分为两个集合三 实验结果边数边数10000200003000040000500000时间29.5775.26121.29223250.33边数边数1000020000300004000050000时间29.57118.28267.3473.12739.25表1 当V= 300时，边数与时间的关系表2 当V= 300时，边数与时间的理论关系顶点数顶点数100200003000040000500000时间5

5、.297.414.616.0619.45表3 当E= 4000时，顶点数与时间的关系顶点数顶点数100200300400500时间5.2910.615.921.226.5表4 当E= 4000时，顶点数与时间的理论关系三 实验结果图 当V= 300时，边数与时间的关系图 当E= 4000时，顶点数与时间的关系从图中看出，实际值与理论值相差较大，因为只是随机的一组数据，难以避免波动和偶然性，下面对多组数据测时间，求平均值。三 实验结果边数边数10000200003000040000500000时间12.2546.5195.45186.33303.366背包容量背包容量1000020000300004000050000时间12.2549110.25196306.25表1 当V= 300时，边数与时间的关系表2 当V= 300时，边数与时间的理论关系顶点数顶点数1002003004005000时间6.8812.1419.6826.2533.71顶点数顶点数10020030000400500时间6.8813.7620.6427.5234.4表3 当E= 4000时，顶点数与时间的关系表4 当E= 4000时，顶点数与时间的理论关系四 实验结