【Ford-Fulkerson標(biāo)號(hào)算法探析綜述3400字】

Ford-Fulkerson標(biāo)號(hào)算法分析綜述目錄TOC\o"1-2"\h\u4191Ford-Fulkerson標(biāo)號(hào)算法分析綜述 1327451.1標(biāo)號(hào)過(guò)程 2258971.給發(fā)點(diǎn)vs標(biāo)號(hào)（0,+∞）。 2246371.2增廣過(guò)程 2233511.更新流量 380871.3算法應(yīng)用 312131.4實(shí)現(xiàn)算法的主要函數(shù) 620312dof[u,v]←0 6189681.5Ford-Fulkerson算法的缺陷 10 Ford-Fulkerson標(biāo)號(hào)算法是一個(gè)最經(jīng)典的基于增廣路徑策略的算法，其基本思路是在網(wǎng)絡(luò)中先找到一個(gè)基本的可行流（一般從零流開(kāi)始）通過(guò)標(biāo)號(hào)方法來(lái)判斷該可行流是否是最大流，如果不是就進(jìn)行流量更新調(diào)整，如果是的話(huà)就可以把直接最大流表示出來(lái)。算法主要分為標(biāo)號(hào)和增廣調(diào)整兩個(gè)過(guò)程：前者通過(guò)標(biāo)號(hào)找出網(wǎng)絡(luò)中是一條增廣路徑；后者沿著標(biāo)號(hào)過(guò)程找到的增廣路徑來(lái)更新路徑上的流量，最終能使網(wǎng)絡(luò)的流量增大。標(biāo)號(hào)標(biāo)號(hào)可行流最大流可行流最大流調(diào)整調(diào)整圖1.1標(biāo)號(hào)算法過(guò)程1.1標(biāo)號(hào)過(guò)程給發(fā)點(diǎn)vs標(biāo)號(hào)（0,+∞）。第一個(gè)數(shù)表明該條弧是前向弧還是后向弧，一般用+號(hào)表示是正向弧，用-號(hào)表示反向弧。第二個(gè)數(shù)是表示對(duì)這個(gè)點(diǎn)，它的改變量可以是多少。對(duì)于發(fā)點(diǎn)而言比較特殊，因?yàn)闆](méi)有前向弧或后向弧，所以用0或Δ表示，而且我們認(rèn)為它可以源源不斷的輸入流量，所以改變量是+∞。取一個(gè)已經(jīng)標(biāo)號(hào)的點(diǎn)vi，采用深度優(yōu)先遍歷對(duì)與vi相鄰的一切未標(biāo)號(hào)的點(diǎn)如果有以vi為起點(diǎn)的?。╲i,vj）是前向弧，且0≤fij≤cij，那么給終點(diǎn)vj標(biāo)號(hào)(+vi，?j)，其中增量?j如果與vi相鄰接的頂點(diǎn)vj之間的弧是反向?。╲j,vi）且是非零流弧，那么給vi標(biāo)記為(-vi,?j)，反向弧上的改變量是該弧上可以減少的量，重復(fù)步驟2，直到匯點(diǎn)vt被標(biāo)號(hào)，或者沒(méi)有頂點(diǎn)可以繼續(xù)標(biāo)號(hào)，則標(biāo)號(hào)過(guò)程結(jié)束。

如果vt被標(biāo)號(hào)，說(shuō)明在剩余網(wǎng)絡(luò)中找到了一條增廣鏈，轉(zhuǎn)到流量調(diào)整過(guò)程

如果1.2增廣過(guò)程設(shè) δ1是從源點(diǎn)vs到匯點(diǎn)vδ1=min{cij-fij，?i|δ2是從源點(diǎn)vs到匯點(diǎn) δ2=min{fij，?i| δ=min{δ1更新流量令fij'=清除上述過(guò)程的所有標(biāo)號(hào)，再重復(fù)標(biāo)號(hào)過(guò)程，對(duì)新得到的可行流進(jìn)行重新標(biāo)號(hào)尋找增廣路。1.3算法應(yīng)用生活中許多復(fù)雜的問(wèn)題在經(jīng)過(guò)適當(dāng)?shù)霓D(zhuǎn)換后都可以轉(zhuǎn)化為最大流問(wèn)題來(lái)求解，如生活中的物資運(yùn)輸、物資轉(zhuǎn)運(yùn)、原油輸送等實(shí)際問(wèn)題，最大流問(wèn)題在其中有很好的應(yīng)用。下列例子是實(shí)際問(wèn)題的簡(jiǎn)化： 某地區(qū)從發(fā)點(diǎn)s到收點(diǎn)t的輸油網(wǎng)絡(luò)和現(xiàn)有的輸油計(jì)劃（已給初始流，流量f為3+2+4=9）如圖1.2所示，問(wèn)該網(wǎng)絡(luò)是否達(dá)到最大輸油量，如果沒(méi)有，求出最大的輸油量。圖1.2輸油網(wǎng)絡(luò)標(biāo)號(hào)過(guò)程：給發(fā)點(diǎn)s標(biāo)注（0，+∞）,其鄰接點(diǎn)有a、c、d，選取點(diǎn)a，對(duì)于前向?。╯，a），滿(mǎn)足0≤fsa≤csa，δa=min{4-3，+∞}=1，所以給點(diǎn)a標(biāo)號(hào)為（+s，1）。繼續(xù)深度優(yōu)先遍歷，找到a的鄰接點(diǎn)b，前向?。╝，b）是飽和弧，不滿(mǎn)足標(biāo)號(hào)條件，再檢查a的鄰接點(diǎn)c，前向?。╝，c）是非飽和弧，δc=min{3-2，1}=1，故給c點(diǎn)標(biāo)號(hào)（+a，1）。同理，給b點(diǎn)標(biāo)號(hào)（+c，1），給t標(biāo)號(hào)（+b，1），現(xiàn)在，收點(diǎn)t得到了標(biāo)號(hào)，說(shuō)明在剩余網(wǎng)絡(luò)中存在一條增廣鏈，標(biāo)號(hào)結(jié)束。調(diào)整過(guò)程：δ=min{δa，δc，令fij'=調(diào)整結(jié)果如圖1.3，此時(shí)流量調(diào)整到4+2+4=10。圖1.3增廣鏈μ1s->a->c->b->t圖1.4增廣μ對(duì)更新后的圖1.3重新進(jìn)入標(biāo)號(hào)過(guò)程，給發(fā)點(diǎn)s標(biāo)注（0，+∞）,此時(shí)前向弧（s，a）流量已達(dá)到飽和，所以無(wú)法對(duì)a標(biāo)號(hào)。檢查點(diǎn)c，我們可以給c點(diǎn)標(biāo)號(hào)（+s，1），給e標(biāo)號(hào)（+c，1），給t點(diǎn)標(biāo)號(hào)（+e，1），所以，我們又得到一條新的增廣鏈s->c->e->t，沿該增廣鏈進(jìn)行增廣，如圖1.4所示，此時(shí)流量調(diào)整到4+3+4=11。圖1.5增廣μ3s->d->c->e->t圖1.6增廣μ繼續(xù)重復(fù)上述標(biāo)號(hào)過(guò)程尋找增廣鏈然后進(jìn)行流量調(diào)整，如圖1.5、圖1.6。若此時(shí)再進(jìn)行標(biāo)號(hào)，發(fā)現(xiàn)對(duì)s點(diǎn)和d點(diǎn)標(biāo)號(hào)之后，再也找不到滿(mǎn)足標(biāo)號(hào)條件的鄰接點(diǎn)v，標(biāo)號(hào)過(guò)程無(wú)法繼續(xù)進(jìn)行（圖1.7）。匯點(diǎn)t未被標(biāo)號(hào)，則說(shuō)明此時(shí)的流量f=4+3+7=14是該輸油網(wǎng)絡(luò)的最大流量。圖1.7最大流與最小割在上圖中，標(biāo)號(hào)結(jié)束后所有的頂點(diǎn)被劃分成兩類(lèi)：已經(jīng)標(biāo)號(hào)的頂點(diǎn)和未被標(biāo)號(hào)的頂點(diǎn)。已標(biāo)號(hào)點(diǎn)集合S{s，d}，未標(biāo)號(hào)點(diǎn)集合S{a，b，c，e，t}，所以在求得該網(wǎng)絡(luò)最大流的同時(shí)我們也得到了該網(wǎng)絡(luò)的最小割集(S,S)={（s，a）、（s，c）、（d，c）、（d，e）}，最小割的容量=csa+csc+cdc+1.4實(shí)現(xiàn)算法的主要函數(shù)Ford-Fulkerson算法的偽代碼如下，F(xiàn)ORD-FULKERSON(G,s,t)1foreachedge(u,v)∈E[G]2dof[u,v]←03f[v,u]←04whilethereexistsapathpfromstotintheresidualnetworkGf5docf(p)←min{cf(u,v):(u,v)isinp}6foreachedge(u,v)inp7dof[u,v]←f[u,v]+cf(p)8f[v,u]←-f[u,v]第1~3行目的是將各條邊的流量初始化為0，從零流開(kāi)始尋找增廣路，最后幾行是一直在殘留網(wǎng)絡(luò)Gf主要函數(shù)實(shí)現(xiàn)如下，由于篇幅限制，以下只列出幾個(gè)重要的函數(shù)，其他部分代碼放在附錄中。尋找增廣路徑的函數(shù)作用是判斷是否存在增廣路，若存在，則流量還有增加的可能。boolfindPath(void){memset(path,0,nodecnt); //初始化存放路徑的數(shù)組，nodecnt是節(jié)點(diǎn)數(shù)量boolvisited[MAX_NODE];//visited數(shù)組記錄是否訪(fǎng)問(wèn)過(guò)該節(jié)點(diǎn)memset(visited,false,nodecnt);//初始化，一開(kāi)始，所有節(jié)點(diǎn)沒(méi)有被訪(fǎng)問(wèn)pathLength=0; //初始化當(dāng)前的路徑長(zhǎng)度intsrc=0; //s-t路徑的源節(jié)點(diǎn)(s)path[pathLength]=src;//通過(guò)DFS搜索相鄰找到s-t路徑，如果有一個(gè)s-t路徑，返回truereturn(dfs(src,visited)); }深度優(yōu)先遍歷函數(shù)深度優(yōu)先遍歷就像走迷宮，如果想要找到出口，可以從開(kāi)始的位置先選擇任意一個(gè)岔路口，一條路走到黑，直到該岔路無(wú)法繼續(xù)前進(jìn)。此時(shí)原路返回，退回到上一個(gè)岔路口，然后選擇另一個(gè)方向繼續(xù)一條路走到黑。重復(fù)以上過(guò)程，直到找到出口。booldfs(intsrc,bool*visited){if(src==nodecnt-1)//如果當(dāng)前是目標(biāo)(t)，則找到s-t路徑returntrue;visited[src]=true;for(intdest=0;dest<nodecnt;dest++)//搜索與src相鄰的{if(edge[src][dest]>0&&!visited[dest])//找到未訪(fǎng)問(wèn)過(guò)的鄰近{pathLength+=1; //當(dāng)前路徑長(zhǎng)度+1path[pathLength]=dest;//將此相鄰添加到s-t路徑//繼續(xù)搜索相鄰if(!dfs(dest,visited)){//如果當(dāng)前的相鄰不能到達(dá)最終的目標(biāo)，路徑長(zhǎng)度減小，因?yàn)樗崆霸黾恿藀athLength-=1;continue;//繼續(xù)調(diào)查下一個(gè)相鄰}else{returntrue;//如果當(dāng)前的相鄰能夠到達(dá)最終的目標(biāo)}}elseif(dest==nodecnt-1)//沒(méi)有相鄰，意味著沒(méi)有s-t路徑returnfalse;}return0;}求最小剩余容量的函數(shù)該函數(shù)在已找到增廣路的基礎(chǔ)上，遍歷其找到該增廣路上的流量瓶頸，即還能增加多少流量取決于該路徑上所有弧中剩余流量的最小值。intfind_delta(void){intdelta=INF;//初始化最小容量for(inti=0;i<pathLength-1;i++){if(delta>edge[path[i]][path[i+1]])//如果s-t上邊的流量小于當(dāng)前最小容量{delta=edge[path[i]][path[i+1]];//則更新最小容量}}returndelta;}根據(jù)s-t路徑更新剩余網(wǎng)絡(luò)的函數(shù)根據(jù)流量調(diào)整規(guī)則，該增廣路徑上的所有前向弧加上delta，所有后向弧減去deltavoidupdate(void){intsrc=0;intdest=0;intdelta=find_delta();//找到增廣路徑上的最小流量flow+=delta;//更新最大流量for(inti=0;i<pathLength-1;i++){src=path[i];dest=path[i+1];edge[src][dest]-=delta;//前向弧加上deltaedge[dest][src]+=delta;//后向弧減去delta}}對(duì)于1.3中的問(wèn)題，應(yīng)用上述代碼，由于程序開(kāi)始時(shí)會(huì)把所有的弧上的流量初始化為零，所以在尋找增廣路時(shí)是從可行流是零流開(kāi)始找所有增廣路的，最終運(yùn)行結(jié)果如下：增廣路1：s->a->b->tdelta=1增廣路2：s->a->c->b->tdelta=3增廣路3：s->c->b->tdelta=1增廣路4：s->c->e->b->tdelta=2增廣路5：s->d->c->e->tdelta=3增廣路6：s->d->e->tdelta=4該網(wǎng)絡(luò)的最大流量maxflow=141.5Ford-Fulkerson算法的缺陷從上面程序運(yùn)行結(jié)果也可以看出，F(xiàn)ord-Fulkerson算法在尋找增廣路時(shí)具有任意性，并不能保證每次找到的增廣路都是最短路徑，雖然最終都能求解出最大流，但是在一些特殊的網(wǎng)絡(luò)中，這樣任意尋找增廣路的策略可能會(huì)極其的耗費(fèi)時(shí)間，造成極低的效率。以圖1.8為例，初始流是0，弧邊上的數(shù)字代表該條弧的容量，在這樣一個(gè)特殊的容量網(wǎng)絡(luò)中，我們一眼可以看出最大流是9999（s->u->t）+9999（s->v->t），但Ford-Fulkerson算法如果是不斷重復(fù)選取s->u->v->t和s->v->u->t做為增廣路徑，每次只能增加1個(gè)單位流量，最終需要重復(fù)19998次才能達(dá)到最大流量。這是個(gè)非常低效的過(guò)程，并且當(dāng)圖中弧的容量變成更大的數(shù)時(shí)，這