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

《最短增益路徑法求解最大流問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、深圳大學(xué)實(shí)驗(yàn)報(bào)告課程名稱:算法分析與復(fù)雜性理論實(shí)驗(yàn)項(xiàng)目名稱:實(shí)驗(yàn)五最短增益路徑法求解最大流問題學(xué)院:計(jì)算機(jī)與軟件學(xué)院專業(yè)：軟件工程指導(dǎo)教師:學(xué)號(hào)班級(jí):實(shí)驗(yàn)時(shí)間：2015?10?22實(shí)驗(yàn)報(bào)告提交時(shí)間：2015U30教務(wù)部制??實(shí)驗(yàn)?zāi)康?.掌握最短增益路徑法思想。2.學(xué)會(huì)最大流問題求解方法。二.實(shí)驗(yàn)步驟與結(jié)果實(shí)驗(yàn)總體思路：通過capacity]][]二維數(shù)組存儲(chǔ)對應(yīng)邊的容量，并用兩個(gè)一維數(shù)組分別保存邊的剩余流量和路徑上當(dāng)前節(jié)點(diǎn)的前驅(qū)。用C++中的queue類實(shí)現(xiàn)隊(duì)列的相關(guān)操作，進(jìn)而實(shí)現(xiàn)BFS算法。輸入冇向圖中邊的個(gè)數(shù)和頂點(diǎn)個(gè)數(shù)Z后，通過一個(gè)for循

2、環(huán)獲取對應(yīng)邊的始點(diǎn)、終點(diǎn)和容量，并將這些數(shù)據(jù)保存到capacity[][]數(shù)組屮。程序設(shè)計(jì)中將源點(diǎn)設(shè)為1,將匯點(diǎn)設(shè)為最后一個(gè)頂點(diǎn)。(代碼和結(jié)果如下圖所示)。各排序算法的實(shí)現(xiàn)及實(shí)驗(yàn)結(jié)果：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找一條最短的增廣路徑，然后沿著這條路徑修改流量值（實(shí)際修改的是殘量網(wǎng)絡(luò)的邊權(quán)）。當(dāng)沒有增廣路時(shí)，算法停止

9、，此時(shí)的流就是最大。實(shí)驗(yàn)結(jié)果:"C:UsersLaiDesktopM)^^^fi.exe1A—y.B、戈7IA4八一別1<<<<曰疋迭迭迭迭祐8次次次次煙61234-4,/5第第第啻取大大大大曰>>>販的的的一WUW!路（注：由于是根據(jù)前驅(qū)來找路徑的，故輸出路徑為（終點(diǎn)，始點(diǎn)，容量）。）第1次迭代：（6,3,4）、（3,2,4）、（2,1,4）245第4次迭代：（6,3,2）、（3,2,2）、（2,1,2）厶、▲總結(jié):根據(jù)通信網(wǎng)絡(luò)中邊的個(gè)數(shù)和頂點(diǎn)個(gè)數(shù)n=

10、V

11、,m=

12、E

13、,每進(jìn)行一次增廣BFS搜索算法，效率為0（m）,而在最壞的情況卜

14、?需耍（n-2）增廣（即除源點(diǎn)和匯點(diǎn)外其他點(diǎn)都沒有連通，所有點(diǎn)都只和s與t連通）。所以,最短增益路徑法的時(shí)間復(fù)雜度為OWn）,這在稀疏圖中效率比較高。四.實(shí)驗(yàn)心得解決一個(gè)問題最重要的是理解它的解題算法，只冇掌握解題的思路，才能使得程序的實(shí)現(xiàn)事半功倍。Edmonds-Karp算法實(shí)際上就是采用廣度優(yōu)先搜索來實(shí)現(xiàn)對增廣路徑的計(jì)算，這種算法思想在很多方面都有應(yīng)用。實(shí)驗(yàn)過程難免會(huì)遇到問題，掌握好的調(diào)試技巧能夠快速查找出問題的所在，并通過排查，逐一改正程序中存在的問題，不管用什么編譯器，都耍學(xué)會(huì)設(shè)置適當(dāng)?shù)臄帱c(diǎn)。遇到不懂的地方要多查看相關(guān)的書籍或者在網(wǎng)上查

15、找資料，這樣才能真正學(xué)到東四。附件：源碼#includettinclude#includeusingnamcspaccstd;ttdefinearraysize201intmaxData=0x7fffffff;intcapacity[arraysize][arraysize];intfl()w[arraysi7e];少流量可用intpre[arraysize];同時(shí)標(biāo)記該節(jié)點(diǎn)是否在隊(duì)列中intn,m;queuemyqueue;intBFS(intsrc,intdes){inti,j

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