最短增益路徑法求解最大流問(wèn)題

最短增益路徑法求解最大流問(wèn)題

ID:44545332

大小:269.30 KB

頁(yè)數(shù):7頁(yè)

時(shí)間:2019-10-23

最短增益路徑法求解最大流問(wèn)題_第1頁(yè)
最短增益路徑法求解最大流問(wèn)題_第2頁(yè)
最短增益路徑法求解最大流問(wèn)題_第3頁(yè)
最短增益路徑法求解最大流問(wèn)題_第4頁(yè)
最短增益路徑法求解最大流問(wèn)題_第5頁(yè)
資源描述:

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

1、深圳大學(xué)實(shí)驗(yàn)報(bào)告課程名稱:算法分析與復(fù)雜性理論實(shí)驗(yàn)項(xiàng)目名稱:實(shí)驗(yàn)五最短增益路徑法求解最大流問(wè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ì)最大流問(wèn)題求解方法。二.實(shí)驗(yàn)步驟與結(jié)果實(shí)驗(yàn)總體思路:通過(guò)capacity]][]二維數(shù)組存儲(chǔ)對(duì)應(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后,通過(guò)一個(gè)for循

2、環(huán)獲取對(duì)應(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];算法說(shuō)明:每次用BFS找一條最短的增廣路徑,然后沿著這條路徑修改流量值(實(shí)際修改的是殘量網(wǎng)絡(luò)的邊權(quán))。當(dāng)沒(méi)有增廣路時(shí),算法停止

9、,此時(shí)的流就是最大。實(shí)驗(yàn)結(jié)果:"C:UsersLaiDesktopM)^^^fi.exe1A—y.B、戈7IA4八一別1<<<<曰疋迭迭迭迭祐8次次次次煙61234-4,/5第第第啻取大大大大曰>>>販的的的一WUW!路(注:由于是根據(jù)前驅(qū)來(lái)找路徑的,故輸出路徑為(終點(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)都沒(méi)有連通,所有點(diǎn)都只和s與t連通)。所以,最短增益路徑法的時(shí)間復(fù)雜度為OWn),這在稀疏圖中效率比較高。四.實(shí)驗(yàn)心得解決一個(gè)問(wèn)題最重要的是理解它的解題算法,只冇掌握解題的思路,才能使得程序的實(shí)現(xiàn)事半功倍。Edmonds-Karp算法實(shí)際上就是采用廣度優(yōu)先搜索來(lái)實(shí)現(xiàn)對(duì)增廣路徑的計(jì)算,這種算法思想在很多方面都有應(yīng)用。實(shí)驗(yàn)過(guò)程難免會(huì)遇到問(wèn)題,掌握好的調(diào)試技巧能夠快速查找出問(wèn)題的所在,并通過(guò)排查,逐一改正程序中存在的問(wèn)題,不管用什么編譯器,都耍學(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;}//記錄殘留

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。