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

1、算法設(shè)計(jì)與分析實(shí)驗(yàn)四 最短增益路徑法求解最大流問題問題一 問題 對(duì)于給定的通信網(wǎng)絡(luò)，該網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的路徑流量給定，如何求解該網(wǎng)絡(luò)的最大流量，并進(jìn)行流量分配？圖的生成V = 4 E = 51s234t三 最大流最小割 設(shè)f是源點(diǎn)為s，匯點(diǎn)為t的流網(wǎng)絡(luò)G中的流。并且(S,T)是G的一個(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|任意割的凈流都是相等的對(duì)于流網(wǎng)絡(luò)G中任意流f，其值的上界為G的任意割的容量證明:設(shè)(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 從包含源點(diǎn)的集合到包含匯點(diǎn)的集合的出度的最小值，即為最小割，也為最大流。三 最大流最小割開始頂點(diǎn)求解頂點(diǎn)

4、求解求解求解001101 用樹的深度遍歷將所有頂點(diǎn)分為兩個(gè)集合，其中一個(gè)集合包含源點(diǎn)，另外一個(gè)集合包含匯點(diǎn)，然后求出從包含源點(diǎn)的集合到包含匯點(diǎn)的集合的出度的最小值，即為最小割，也為最大流。將頂點(diǎn)分為兩個(gè)集合三 實(shí)驗(yàn)結(jié)果邊數(shù)邊數(shù)10000200003000040000500000時(shí)間29.5775.26121.29223250.33邊數(shù)邊數(shù)1000020000300004000050000時(shí)間29.57118.28267.3473.12739.25表1 當(dāng)V= 300時(shí)，邊數(shù)與時(shí)間的關(guān)系表2 當(dāng)V= 300時(shí)，邊數(shù)與時(shí)間的理論關(guān)系頂點(diǎn)數(shù)頂點(diǎn)數(shù)100200003000040000500000時(shí)間5

5、.297.414.616.0619.45表3 當(dāng)E= 4000時(shí)，頂點(diǎn)數(shù)與時(shí)間的關(guān)系頂點(diǎn)數(shù)頂點(diǎn)數(shù)100200300400500時(shí)間5.2910.615.921.226.5表4 當(dāng)E= 4000時(shí)，頂點(diǎn)數(shù)與時(shí)間的理論關(guān)系三 實(shí)驗(yàn)結(jié)果圖 當(dāng)V= 300時(shí)，邊數(shù)與時(shí)間的關(guān)系圖 當(dāng)E= 4000時(shí)，頂點(diǎn)數(shù)與時(shí)間的關(guān)系從圖中看出，實(shí)際值與理論值相差較大，因?yàn)橹皇请S機(jī)的一組數(shù)據(jù)，難以避免波動(dòng)和偶然性，下面對(duì)多組數(shù)據(jù)測(cè)時(shí)間，求平均值。三 實(shí)驗(yàn)結(jié)果邊數(shù)邊數(shù)10000200003000040000500000時(shí)間12.2546.5195.45186.33303.366背包容量背包容量1000020000300004000050000時(shí)間12.2549110.25196306.25表1 當(dāng)V= 300時(shí)，邊數(shù)與時(shí)間的關(guān)系表2 當(dāng)V= 300時(shí)，邊數(shù)與時(shí)間的理論關(guān)系頂點(diǎn)數(shù)頂點(diǎn)數(shù)1002003004005000時(shí)間6.8812.1419.6826.2533.71頂點(diǎn)數(shù)頂點(diǎn)數(shù)10020030000400500時(shí)間6.8813.7620.6427.5234.4表3 當(dāng)E= 4000時(shí)，頂點(diǎn)數(shù)與時(shí)間的關(guān)系表4 當(dāng)E= 4000時(shí)，頂點(diǎn)數(shù)與時(shí)間的理論關(guān)系四 實(shí)驗(yàn)結(jié)