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