算法分析與復(fù)雜性理論 實驗報告 最大流問題

1、深 圳 大 學(xué) 實 驗 報 告課程名稱： 算法分析與復(fù)雜性理論 實驗名稱： 實驗五 最短增益路徑法求最大流問題 學(xué)院： 計算機與軟件學(xué)院 專業(yè)： 軟件工程 報告人： 文成 學(xué)號： 2150230509 班級： 學(xué)術(shù)型 同組人： 無 指導(dǎo)教師： 楊烜 實驗時間： 2015/11/232015/11/30 實驗報告提交時間： 2015/11/28 教務(wù)處制一 實驗?zāi)康呐c實驗內(nèi)容實驗?zāi)康模海?）掌握最短增益路徑法思想。（2）學(xué)會最大流問題求解方法。實驗內(nèi)容：1. 給定下面的通信網(wǎng)絡(luò)，該網(wǎng)絡(luò)中各節(jié)點之間的路徑流量給定，使用最短增益路徑法求解該網(wǎng)絡(luò)的最大流量，并進行流量分配。2.要求用加權(quán)矩陣輸入該網(wǎng)絡(luò)

2、，輸出每次迭代過程中的最大流量及各路徑分配的流量。3.如果能利用圖形界面輸出動態(tài)求解過程（在網(wǎng)絡(luò)結(jié)構(gòu)的圖形顯示中，標注每一次求得的增益路徑，并顯示當前流量分配），可獲加分。算法思想提示：1.利用二維數(shù)組Ci,j和Fi,j分別存放容量和流量。2.構(gòu)建隊列類Queue，該類具有取隊首元素，加入隊尾元素等方法。3.具體算法過程參見教材pp.271-272二實驗步驟最大流問題的問題描述：如上圖。s是源點，t為匯點，每條邊上數(shù)字的含義是邊能夠允許流過的最大流量。可以將邊看成管道，3代表該管道每秒最多能通過3個單位的流量。最大流問題即是說，從s點到t點，最大允許流量是多少？最大流問題的算法思想：最短增益路

3、徑法(先標記先掃描算法)：用兩個記號來標記一個新的頂點第一個標記指出從源點到被標記頂點還能增加多少流量第二個標記指出另一個頂點的名字，可加上+或-來表示頂點時通過前向邊還是后向邊訪問到的算法及其偽代碼：Maxflow (G)/最短增量路徑算法的實現(xiàn)/輸入：網(wǎng)絡(luò)G，具有一個源點1和一個匯點n，每條邊（i，j）的容量都是正整數(shù)Uij/輸出：最大流量x/對網(wǎng)絡(luò)中的每條邊（i，j），設(shè)xij=0/把源點標記為，-，再把源點加入到空隊列Q中While not Empty(Q) doiFront(Q);Dequeue(Q)for 從i到j(luò)的每條邊do/前向邊if j 沒有被標記rij uij - xiji

4、f rij 0Lj minLi,xji;用L，i-來標記jEnqueue(Q,j)If 匯點被標記了/沿著找到的增益路徑進行增量jn/從匯點開始，用第二個標記反向移動while j!=i/沒有到達源點if 頂點j的第二個標記是i+xijxij+Lnelse/頂點j的第二個標記是i-xjixji-Lnji；ii的第二個標記指出的頂點除了源點，擦去所有頂點的標記用源點對Q重新初始化return x/當前流量是最大的思路以及代碼解釋：（全部源代碼見附件）先創(chuàng)建一個解決問題的類，命名為G。計算最大流作為這個類中的一個方法來實現(xiàn)。利用二維數(shù)組Mapi,j和Flowi,j分別存放容量和流量。添加頭文件#i

5、nclude ，后面需要用到隊列，需要該類的取隊首元素，加入隊尾元素等方法。class Gpublic:G();G(int n,int start,int end);void Edge(int a,int b,int flow); /頂點a和頂點b之間的流量void Maxflow(); /計算最大流private:int N; /頂點個數(shù)intStart; /源點intEnd, /匯點*Map, /網(wǎng)絡(luò)容量*Flow, /通過流量*Rest, /剩余流量*Pre, /標記流向,正為前向,負為后向*Sign, /頂點是否標記,0為未標記,1為已標記*P; /過程變量,記錄流量bool Sign

6、N(); /標記頂點int Min(int a,int b); /計算最小值void Update(); /更新網(wǎng)絡(luò);構(gòu)造函數(shù)就先定義兩個G:G() Pre=NULL; /不帶參數(shù)的構(gòu)造函數(shù)G:G(int n,int start,int end) /帶三個參數(shù)的構(gòu)造函數(shù)，頂點個數(shù)，源點和匯點初始化在類G中，實現(xiàn)了void Maxflow();方法，用來計算最大流，其中標記頂點的函數(shù)定義為bool SignN();bool G:SignN()/標記頂點Update();/更新queue que;/創(chuàng)建一個隊列的對象que.push(Start);/把源點放進隊列里面SignStart=1;/將源

7、點標記PStart=1000;PreStart=-1;/標記流向為后向while(!que.empty()/While not Empty(Q) doint head=que.front();/不斷地取隊首為headque.pop();for(int i=1;i0 & Signi=0)/如果從head出發(fā)到其它頂點，有剩余流量大于0，并且沒有被標記Pi=Min(Phead,Restheadi);Prei=head;Signi=1;if(i=End) return true;/當掃描到匯點后返回que.push(i);for(i=1;i0 & Signi=0)/如果有頂點到head的流量大于0.

8、并且沒有被標記Pi=Min(Phead,Flowihead);Prei=-head;Signi=1;if(i=End) return true;/當掃描到匯點后返回que.push(i); return false;void G:Maxflow()/計算最大流int maxflow=0;while(SignN()/迭代地去標記頂點maxflow=maxflow+PEnd;for(int i=End;i1;i=abs(Prei)if(Prei0)/流向為前向FlowPreii=FlowPreii+PEnd;if(Prei0)/流向為后向Flowiabs(Prei)=Flowiabs(Prei)-

9、PEnd;cout最大流:maxflow236，一條4的通路。此時流量為4此時流量為6。此時流量為8。此時流量為10下一次迭代之后，流量沒有增長，那么結(jié)束。最后的結(jié)果應(yīng)該是這樣的。最大流量為10由最大流最小割定理可以驗證。該圖的最小割為(2,5) (3,6) (4,5)，最小割流量為2+4+4=10。因為網(wǎng)絡(luò)中的最大流量值等于它最小割的容量，可以驗證上圖的正確性。后面，我也實現(xiàn)了用加權(quán)矩陣輸入該網(wǎng)絡(luò)，輸出每次迭代過程中的最大流量及各路徑分配的流量。四 實驗心得在現(xiàn)實生活中，在實際的網(wǎng)絡(luò)中，網(wǎng)絡(luò)的結(jié)點和邊都是有容量限制的. 很多情況下我們需要知道在一個有容量限制的網(wǎng)絡(luò)中兩個指定結(jié)點（分別稱為源點和匯點）之間最多能傳輸多少流量，并確定達到這個最大流量的傳輸策略. 網(wǎng)絡(luò)最大流問題（簡稱最大流問題）就是描述這個問題的數(shù)學(xué)模型.求解最大流的算法有不少，在此次實驗中，我學(xué)習(xí)到了最短增益路徑法，也明白了，最大流量值和最小割容量是相等的。本次實驗挺有難度的，讓我明白了最大流問題的算法，對迭代改進算法的認識也更加深刻了。這次實驗