【文章內(nèi)容簡介】 dmondsKarp修正算法的實質(zhì)也是一種分層，如果說FordFulkerson算法是采用了深度優(yōu)先策略。EdmondsKarp修正算法則是用寬度優(yōu)先取代了深度優(yōu)先，Dinic算法則是兼取這兩種方法。在分層時用的寬度優(yōu)先法，而尋求增廣路徑時則采用深度優(yōu)先策略（參見文獻[3]）。 增量網(wǎng)絡(luò)與分層增量網(wǎng)絡(luò) 定義13：給定一個帶發(fā)點和收點的容量網(wǎng)絡(luò)及上的可行流后，我們定義，因為中任何一對頂點之間至多有一條弧，所以，記，并且對一切令，于是得一個帶發(fā)點和收點的容量網(wǎng)絡(luò)，稱之為的關(guān)于可行流的增量網(wǎng)絡(luò)。為了介紹分層增量網(wǎng)絡(luò)，我們先來介紹關(guān)于網(wǎng)絡(luò)的一個算法——分層算法，它的基本思想是：步驟0：把發(fā)點標(biāo)為“已標(biāo)號未檢查”，的層數(shù)。步驟1：在已標(biāo)號未檢查頂點中選取最早得到標(biāo)號的頂點，轉(zhuǎn)步驟2；如果所有標(biāo)號頂點都已檢查，轉(zhuǎn)步驟3。步驟2：考察頂點的一切出弧，若已標(biāo)號，什么也不做；否則將標(biāo)為“已標(biāo)號未檢查”，并令。當(dāng)?shù)乃谐龌《伎疾焱戤?，把改為已檢查，轉(zhuǎn)步驟1。步驟3：如果有—些頂點沒有標(biāo)號，則從到這些頂點不存在路；否則為的根，為中最短路的長。在增量網(wǎng)絡(luò)中應(yīng)用分層算法，可以求出從發(fā)點到其余各頂點的最短路的長，就是頂點（關(guān)于發(fā)點）的層數(shù)。即就是的第層頂點。的第0層只有一個頂點，把頂點分層后，中的弧又可以分為三類：第一類為從第層頂點到第層頂點的?。坏诙悶閺牡趯禹旤c到同一層頂點的??；第三類為從第層頂點到第層頂點的弧（參見文獻[5]）。定義14：對于帶發(fā)點和收點的容量網(wǎng)絡(luò)，設(shè)關(guān)于可行流的增量網(wǎng)絡(luò)，我們定義的子網(wǎng)絡(luò)如下：則稱為的關(guān)于可行流的分層增量網(wǎng)絡(luò)。其中第0層和第層分別只有一個頂點和，的所有弧都是由第層頂點指向第層頂點。 Dinic算法的基本思想及具體步驟Dinic算法的基本思想是：從帶發(fā)點和收點的容量網(wǎng)絡(luò)的任一可行流 (例如零流)開始，構(gòu)造的關(guān)于的分層增量網(wǎng)絡(luò)，在中找一條從到的增廣路徑，對沿進行增廣得到可行流，在中刪去上容量最小的弧，并相應(yīng)修改上弧的容量，得到網(wǎng)絡(luò)，然后可以在中再找一條從到的增廣路徑，對沿進行增廣得到可行流，重復(fù)上述步驟依次得到的可行流，因為只有有限條弧，每次至少刪去一條弧，所以在有限步后必然使余下的網(wǎng)絡(luò)不再存在增廣路徑，在中的層數(shù)一定大于它在中的層數(shù)；針對重復(fù)上面的做法，在有限次增廣后一定會得到的可行流，使在中的層數(shù)更大。由于的層數(shù)最多為（是網(wǎng)絡(luò)的頂點數(shù)）。因此經(jīng)過有限步后得到的可行流，中不再有的增廣鏈，這時就是的最大流。Dinic算法的具體步驟如下：步驟0：在網(wǎng)絡(luò)中任意取—個可行流作為初始可行流，令。步驟1：(作分層增量網(wǎng)絡(luò))根據(jù)作的增量網(wǎng)絡(luò)，再利用分層算法構(gòu)造分層增量網(wǎng)絡(luò)，如果在作分層增量網(wǎng)絡(luò)時得不到標(biāo)號，則算法結(jié)束，就是的最大流；否則轉(zhuǎn)步驟2。步驟2：(尋找增廣路徑)①給發(fā)點標(biāo)號為，令。②如在沒有出弧，轉(zhuǎn)⑤；否則在中任取的一條出弧，轉(zhuǎn)③。③設(shè)的標(biāo)號為，其中為前面的節(jié)點，令，獲得標(biāo)號 。④如果，轉(zhuǎn)步驟3；否則令，轉(zhuǎn)②。⑤設(shè)的標(biāo)號為，如果，在中刪去的所有入弧，所得的網(wǎng)絡(luò)仍記為，轉(zhuǎn)②；否則置，轉(zhuǎn)步驟1。步驟3：（增廣）從頂點的標(biāo)號中的第二個元素反向追蹤，求出的增廣路徑，在中把上的每條弧的容量改為，刪去容量為0的弧，同時把流增廣為流，把中修改容量和刪去弧后的網(wǎng)絡(luò)記為，置，去掉網(wǎng)絡(luò)中所有頂點的標(biāo)號，轉(zhuǎn)步驟2。第四章 最大流問題的應(yīng)用 鐵路貨運列車的最優(yōu)調(diào)度 問題敘述某地區(qū)A、B兩市之間要修建一鐵路，依據(jù)地勢、環(huán)境、需求等因素，修建鐵路的預(yù)定方案如下：（1）鐵路的運行方式為客車與貨運兼營的雙軌鐵路（單向單軌），在其運行的列車有旅客快車和貨運列車，由于客車的運行時間是國家鐵路部門早已排定的，不可更改，且規(guī)定客運優(yōu)于貨運，即貨車在每站開出前應(yīng)先明確在其到達前方車站前不會被客車趕上，否則在該站等候不能開車。又若貨車的前方到達站如無停車岔道，則貨車從本站開出前應(yīng)明確在其前面兩站的行程中不會被客車趕上否則在本站等候不能開車，余類推。（2）鐵路線內(nèi)有A、B、C、D四個站，各站的岔道數(shù)為.這些岔道可供調(diào)車用，亦可供停車卸貨及洗刷車輛用。（3）按早已排定的旅客快車時刻表，客車每天凌晨2:00從A站開出，以后每隔5小時開出一列，一晝夜共開出5列，當(dāng)天最后一列的開車時間與翌晨第一列的開車時間相隔4小時?？蛙嚨男熊嚂r間在A、B站之間為3小時；在B、C站之間為2小時；在C、D站之間為5小時。（4）在不干擾客車運行的條件下，關(guān)于貨運列車的初步安排為：每天0:00從A站發(fā)出一列，以后每隔2小時發(fā)出一列，貨車的行車時間在A、B站之間為5小時；在B、C站之間為4小時；在C、D站之間為7小時。為了充分發(fā)揮該鐵路線的貨運能力，需要排定一張最優(yōu)的貨車運行時刻表，即要求每天發(fā)出最多的貨運列車且不干擾已排定的客運列車。 問題分析 求解這個問題較為復(fù)雜，但可將其轉(zhuǎn)化為網(wǎng)絡(luò)最大流問題。（1）設(shè)A、B兩市及其間的車站共P個。每個車站有nk條岔道（k=1,2,3…P）,可停放nk列列車。從第k站到第k+1站的行車時間貨車為tk個小時，客車為tk 個小時。設(shè)為火車到達第k站并從第k站開出的時刻設(shè)為客車到達第k站并從第k站開出的時刻設(shè)為貨車到達第k+1站并從第k+1站開出的時刻設(shè)為客車到達第k+1站并從第k+1站開出的時刻于是顯然有 （2）若有公共部分，則稱是相交的，否則成為不相交的。顯然有當(dāng)只相交情況下客車才有可能（并非必然）在第k站與地k+1站間追上貨車。（3）在相交情況下，，：情況Ⅵ為途中貨車追上了客車故不符合題意。情況Ⅰ與情況Ⅱ中在第k站與第k+1站間不發(fā)生在途中追上貨車。而在情況Ⅲ中必發(fā)生在第k站與第k+1站間客車在途中追上貨車。 于是有下列結(jié)論：若內(nèi)，即，則在第k站與第k+1站必發(fā)生客車追上貨車情況。否則在第k站與第k+1站之間不發(fā)生客車追上貨車情況。（4）繪制網(wǎng)絡(luò)圖用（k，）表示第k站處于時刻的狀態(tài)，如在=（k，），（k，）狀態(tài)開出的貨車不會再途中被客車追上，則在圖中表現(xiàn)為（k，）及（k，）兩節(jié)點為起點的兩條水平方向的直線弧，而在（k，）狀態(tài)下開出的貨車會在途中被客車追上，則不能從該點引出水平方向的直線弧（），垂直方向的直線弧并聯(lián)著同一車站的相鄰狀態(tài)。 上圖中各弧旁的數(shù)字為容量，因鐵路線是單向單軌的，故水平方向的弧容量為1，垂直方向的弧的容量為各站的岔道數(shù)量，在列出全部狀態(tài)的網(wǎng)絡(luò)圖中求最大流，此最大流即為允許開出的最多貨運列車數(shù)。 問題求解以貨運列車的運行時間為基礎(chǔ)繪制網(wǎng)絡(luò)圖。（1）令為火車從某站開出或到達某站的時刻。依題意，若不受客車干擾則：=0:00,2:00,4:00……=5:00,7:00,9:00……=9:00,11:00,13:00……=16:00,18:00,20:00……于是貨車在相鄰兩站的運行時間為（若不受客車干擾）：(25點即翌日1點，余類推)(2)令為客車從某站開出或到達某站的時刻，依題意：=2:00,7:00,12:00,17:00,22:00=5:00,10:00,15:00,20:00,25:00(即1:00)=7:00,12:00,17:00,22:00,27:00（即3:00）=12:00,17:00,22:00,27:00（即3:00），32:00（即8:00）于是客車在相鄰兩站之間的運行時間為： （3）比較之內(nèi)。這說明若A站在6:00及16:00開出兩列貨車，則該兩列貨車在到達B站前，必會被客車撞上。故這兩次貨運列車是不可行的。這表示在以貨運列車的運行時刻為基礎(chǔ)的網(wǎng)絡(luò)圖（）中為（A,6:00）及（A，16:00）兩節(jié)點前未引出水平方向的直線弧。該圖的各個節(jié)點中僅注明貨運列車從該站開出或到達該站的時刻，站名省略了。比較,我們發(fā)現(xiàn)之內(nèi)；之內(nèi)。比較,我們發(fā)現(xiàn)之內(nèi)；之內(nèi)，其在圖3中的表示同前。（4）。如前所述，它表示在該時間內(nèi)，貨車在相鄰兩站的行程中不會被客車追上，故可順利地到達前方車站。垂直方向的直線弧的通量表示各站的岔道數(shù)。（5）做網(wǎng)絡(luò)的發(fā)點，并從向A站的各狀態(tài)節(jié)點作輔助弧，輔助弧的容量等于以A站的各狀態(tài)節(jié)點為起點的各弧的容量的總和。作網(wǎng)絡(luò)的收點，并從D站的各狀態(tài)節(jié)點向作輔助弧。輔助弧的容量等于以D站個狀態(tài)節(jié)點為終點的各弧的容量總和。（6）Ⅰ）以零流f={0,0,…………0}為初始流。Ⅱ）以表示圖3中第i行第j列的節(jié)點。用FordFulkerson標(biāo)號法求得以下增廣鏈并按值進行調(diào)整。① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ 以上10條增廣鏈的調(diào)整量均為。用它對初始流（零流）進行調(diào)整后。若對現(xiàn)行流繼續(xù)標(biāo)號，則只有A站的12個狀態(tài)節(jié)點獲得標(biāo)號，即標(biāo)號中斷，不能延伸達。故現(xiàn)行流即為最大流，其流量結(jié)論 在本問題所給條件下各車站一晝夜中能開出的最多貨運列車數(shù)位10列。（貨車一晝夜中在其他各站點的運行及調(diào)度情況可由同圖作類似闡述）①在0:00,8:00,10:00,18:00,20:00,22:00時刻所開出的貨車在各站點均暢通。②在2:00開出的貨車，11:00到達C站時須在岔道內(nèi)停留到13:00方可繼續(xù)前行。③在4:00開出的貨車，9:00到達B站時，須在岔道內(nèi)停留到11