最小費(fèi)用最大流算法舉例

augmentpath

譯為“增廣路”算法，其思想大致如下：

原有網(wǎng)絡(luò)為G，設(shè)有一輔助圖G'，其定義為V(G') = V(G），E(G'）初始值（也就是容量）與E(G）相同。每次操作時(shí)從Source點(diǎn)搜索出一條到Sink點(diǎn)的路徑，然后將該路徑上所有的容量減去該路徑上容量的最小值，然后對(duì)路徑上每一條邊；添加或擴(kuò)大反方向的容量，大小就是剛才減去的容量。一直到?jīng)]有路為止。此時(shí)輔助圖上的正向流就是最大流。

我們很容易覺得這個(gè)算法會(huì)陷入死循環(huán)，但事實(shí)上不是這樣的。我們只需要注意到每次網(wǎng)絡(luò)中由Source到Sink的流都增加了，若容量都是整數(shù)，則這個(gè)算法必然會(huì)結(jié)束。

尋找通路的時(shí)候可以用DFS，BFS最短路等算法。就這兩者來說，BFS要比DFS快得多，但是編碼量也會(huì)相應(yīng)上增加。

增廣路方法可以解決最大流問題，然而它有一個(gè)不可避免的缺陷，就是在極端情況下每次只能將流擴(kuò)大1（假設(shè)容量、流為整數(shù)），這樣會(huì)造成性能上的很大問題，解決這個(gè)問題有一個(gè)復(fù)雜得多的算法，就是預(yù)推進(jìn)算法。

pushlabel

譯為“預(yù)流推進(jìn)”算法。

可以想象在一個(gè)自來水管網(wǎng)的源頭盡可能多的注入水流之后，最多有多少水可以流到匯點(diǎn)去，由網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn)和管道來約束流量。將每個(gè)節(jié)點(diǎn)都看成一個(gè)水站，他的通過能力是有限的不能通過的水只能退回去。

Push-Relabel

譯為壓入與重標(biāo)記算法

除了用各種方法在剩余網(wǎng)絡(luò)中不斷找增廣路（augmenting）的Ford-Fulkerson系的算法外，還有一種求最大流的算法被稱為壓入與重標(biāo)記（Push-Relabel）算法。它的基本操作有：壓入，作用于一條邊，將邊的始點(diǎn)的預(yù)流盡可能多的壓向終點(diǎn)；重標(biāo)記，作用于一個(gè)點(diǎn)，將它的高度（也就是label）設(shè)為所有鄰接點(diǎn)的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快，但是缺點(diǎn)是相對(duì)難以理解。

Relabel-to-Front使用一個(gè)鏈表保存溢出頂點(diǎn)，用Discharge操作不斷使溢出頂點(diǎn)不再溢出。

Discharge的操作過程是：若找不到可被壓入的臨邊，則重標(biāo)記，否則對(duì)臨邊壓入，直至點(diǎn)不再溢出。

算法的主過程是：首先將源點(diǎn)出發(fā)的所有邊充滿，然后將除源和匯外的所有頂點(diǎn)保存在一個(gè)鏈表里，從鏈表頭開始進(jìn)行Discharge，如果完成后頂點(diǎn)的高度有所增加，則將這個(gè)頂點(diǎn)置于鏈表的頭部，對(duì)下一個(gè)頂點(diǎn)開始Discharge。

Relabel-to-Front算法的時(shí)間復(fù)雜度是O(V^3），還有一個(gè)叫Highest Label Preflow Push的算法復(fù)雜度據(jù)說是O(V^2*E^0.5）。我研究了一下HLPP，感覺它和Relabel-to-Front本質(zhì)上沒有區(qū)別，因?yàn)镽elabel-to-Front每次前移的都是高度最高的頂點(diǎn)，所以也相當(dāng)于每次選擇最高的標(biāo)號(hào)進(jìn)行更新。還有一個(gè)感覺也會(huì)很好實(shí)現(xiàn)的算法是使用隊(duì)列維護(hù)溢出頂點(diǎn)，每次對(duì)pop出來的頂點(diǎn)discharge，出現(xiàn)了新的溢出頂點(diǎn)時(shí)入隊(duì)。

Push-Relabel類的算法有一個(gè)名為gap heuristic的優(yōu)化，就是當(dāng)存在一個(gè)整數(shù)0k的頂點(diǎn)v做更新，若它小于V 1就置為V 1。

c 程序舉例

typedef pair P;

struct edge { int to,cap,cost,rev; };

int V;

vector G[MAX_V];

int h[MAX_V];

int dist[MAX_V];

int prevv[MAX_V],preve[MAX_V];

void add_edge(int from,int to,int cap,int cost) {

G[from].push_back((edge){to,cap,cost,G[to].size()});

G[to].push_back((edge){from,0,-cost,G[from].size()-1});

}

int min_cost_flow(int s,int t,int f) {

int res;

fill(h,h V,0);

while(f>0) {

priority_queue ,greater

> que;

fill(dist,dist V,INF);

dist[s]=0;

que.push(P(0,s));

while(!que.empty()) {

P p=que.top();que.pop();

int v=p.second;

if(dist[v]

if(e.cap>0&&dist[e.to]>dist[v] e.cost h[v]-h[e.to]) {

dist[e.to]=dist[v] e.cost h[v]-h[e.to];

prevv[e.to]=v;

preve[e.to]=i;

que.push(P(dist[e.to],e.to));

}

}

}

if(dist[t]==INF) return -1;

for(int v=0;v

for(int v=t;v!=s;v=prevv[v])

d=min(d,G[prevv[v]][preve[v]].cap);

f-=d;

res =d*h[t];

for(int v=t;v!=s;v=prevv[v]) {

edge &e=G[prevv[v]][preve[v]];

e.cap-=d;

G[v][e.rev].cap =d;

}

}

return res;

}2100433B

解決最小費(fèi)用最大流問題，一般有兩條途徑。一條途徑是先用最大流算法算出最大流，然后根據(jù)邊費(fèi)用，檢查是否有可能在流量平衡的前提下通過調(diào)整邊流量，使總費(fèi)用得以減少？只要有這個(gè)可能，就進(jìn)行這樣的調(diào)整。調(diào)整后，得到一個(gè)新的最大流。

然后，在這個(gè)新流的基礎(chǔ)上繼續(xù)檢查，調(diào)整。這樣迭代下去，直至無調(diào)整可能，便得到最小費(fèi)用最大流。這一思路的特點(diǎn)是保持問題的可行性（始終保持最大流），向最優(yōu)推進(jìn)。另一條解決途徑和前面介紹的最大流算法思路相類似，一般首先給出零流作為初始流。這個(gè)流的費(fèi)用為零，當(dāng)然是最小費(fèi)用的。然后尋找一條源點(diǎn)至匯點(diǎn)的增流鏈，但要求這條增流鏈必須是所有增流鏈中費(fèi)用最小的一條。如果能找出增流鏈，則在增流鏈上增流，得出新流。將這個(gè)流做為初始流看待，繼續(xù)尋找增流鏈增流。這樣迭代下去，直至找不出增流鏈，這時(shí)的流即為最小費(fèi)用最大流。這一算法思路的特點(diǎn)是保持解的最優(yōu)性（每次得到的新流都是費(fèi)用最小的流），而逐漸向可行解靠近（直至最大流時(shí)才是一個(gè)可行解）。

由于第二種算法和已介紹的最大流算法接近，且算法中尋找最小費(fèi)用增流鏈，可以轉(zhuǎn)化為一個(gè)尋求源點(diǎn)至匯點(diǎn)的最短路徑問題，所以這里介紹這一算法。

在這一算法中，為了尋求最小費(fèi)用的增流鏈，對(duì)每一當(dāng)前流，需建立伴隨這一網(wǎng)絡(luò)流的增流網(wǎng)絡(luò)。例如圖 1 網(wǎng)絡(luò)G 是具有最小 費(fèi)用的流，邊旁參數(shù)為c(e),f(e),w(e），而圖 2 即為該網(wǎng)絡(luò)流 的增流網(wǎng)絡(luò)G′。增流網(wǎng)絡(luò)的頂點(diǎn)和原網(wǎng)絡(luò)相同。按以下原則建 立增流網(wǎng)絡(luò)的邊：若G中邊（u，v）流量未飽，即f(u,v) < e(u,v），則G ' 中建邊（u,v），賦權(quán)w ' (u,v)=w(u,v）；若G中邊（u,v）已有流量，即f(u,v）〉0，則G′中建邊（v,u），賦權(quán)w′（v,u) =-w(u,v）。建立增流網(wǎng)絡(luò)后，即可在此網(wǎng)絡(luò)上求源點(diǎn)至匯點(diǎn)的最短路徑，以此決定增流路徑，然后在原網(wǎng)絡(luò)上循此路徑增流。這里，運(yùn)用的仍然是最大流算法的增流原理，唯必須選定最小費(fèi)用的增流鏈增流。

計(jì)算中有一個(gè)問題需要解決。這就是增流網(wǎng)絡(luò)G ′中有負(fù)權(quán)邊，因而不能直接應(yīng)用標(biāo)號(hào)法來尋找x至y的最短路徑，采用其它計(jì)算有負(fù)權(quán)邊的網(wǎng)絡(luò)最短路徑的方法來尋找x至y的最短路徑，將 大大降低計(jì)算效率。為了仍然采用標(biāo)號(hào)法計(jì)算最短路徑，在每次建立增流網(wǎng)絡(luò)求得最短路徑后，可將網(wǎng)絡(luò)G的權(quán)w(e）做一次修正，使再建的增流網(wǎng)絡(luò)不會(huì)出現(xiàn)負(fù)權(quán)邊，并保證最短路徑不至于因此而改變。下面介紹這種修改方法。當(dāng)流值為零，第一次建增流網(wǎng)絡(luò)求最短路徑時(shí)，因無負(fù)權(quán)邊，當(dāng)然可以采用標(biāo)號(hào)法進(jìn)行計(jì)算。為了使以后建立增流網(wǎng)絡(luò)時(shí)不出現(xiàn)負(fù)權(quán)邊，采取的辦法是將 G中有流邊（f(e)>0）的權(quán)w(e）修正為0。為此， 每次在增流網(wǎng)絡(luò)上求得最短路徑后，以下式計(jì)算G中新的邊權(quán)w " (u,v）：

w " (u,v)=L(u)-L(v) w(u,v) (*)

式中 L(u),L(v) -- 計(jì)算G′的x至y最短路徑時(shí)u和v的標(biāo)號(hào)值。第一次求最短徑時(shí)如果（u,v）是增流路徑上的邊， 則據(jù)最短 路徑算法一定有 L(v)=L(u) w ' (u,v)=L(u) w(u,v）， 代入（*）式必有

w″（u,v)=0。

如果（u,v）不是增流路徑上的邊，則一定有：

L(v）≤L(u) w(u,v）， 代入（*）式則有 w(u,v）≥0。

可見第一次修正w(e）后，對(duì)任一邊，皆有w(e）≥0， 且有流 的邊（增流鏈上的邊），一定有w(e)=0。以后每次迭代計(jì)算，若 f(u,v)>0，增流網(wǎng)絡(luò)需建立（v,u）邊，邊權(quán)數(shù)w ' (v,u)=-w(u,v) =0，即不會(huì)再出現(xiàn)負(fù)權(quán)邊。 此外，每次迭代計(jì)算用（*）式修正一切w(e）， 不難證明對(duì)每一條x至y的路徑而言，其路徑長度都同樣增加L(x)-L(y）。因此，x至y的最短路徑不會(huì)因?qū)(e）的修正而發(fā)生變化。

【計(jì)算步驟】

⒈ 對(duì)網(wǎng)絡(luò)G=[V,E,C,W]，給出流值為零的初始流。

⒉ 作伴隨這個(gè)流的增流網(wǎng)絡(luò)G′=[V′，E′，W′]。G′的頂點(diǎn)同G：V′=V。若G中f(u,v)0，則G′中建邊（v,u），w′（v,u)=-w(u,v）。

⒊ 若G′不存在x至y的路徑，則G的流即為最小費(fèi)用最大流， 停止計(jì)算；否則用標(biāo)號(hào)法找出x至y的最短路徑P。

⒋ 根據(jù)P，在G上增流：對(duì)P的每條邊（u,v），若G存在（u,v），則（u,v）增流；若G存在（v,u），則（v,u）減流。增（減）流后，應(yīng)保證對(duì)任一邊有c(e）≥ f(e）≥0。

⒌ 根據(jù)計(jì)算最短路徑時(shí)的各頂點(diǎn)的標(biāo)號(hào)值L(v），按下式修 改G一切邊的權(quán)數(shù)w(e):

L(u)-L(v) w(e）→w(e）。

⒍ 將新流視為初始流，轉(zhuǎn)2。

前向弧和后向弧

在網(wǎng)絡(luò)D(V,A) 中,如果對(duì)連接發(fā)點(diǎn)vs和收點(diǎn)vt 的一條鏈P，方向規(guī)定為從vs 到vt，則當(dāng)鏈P 中弧(vi,vj)

的方向與規(guī)定的方向一致時(shí)，稱?。╲i,vj) 為前向弧，否則稱為后向弧。不在這條鏈上的弧，不定義前向弧和后向弧。

可擴(kuò)充鏈

設(shè){fij}為一可行流（假設(shè)為非負(fù)值），如果存在從發(fā)點(diǎn)vs 到收點(diǎn)vt 的鏈P，在鏈P 上，下列兩條同時(shí)滿足，則稱P 為可擴(kuò)充鏈：

①對(duì)于P 上的前向?。╲i,vj) 有fij

②對(duì)于P 上的后向弧（vi,vj) 有fij>0。

可擴(kuò)充鏈P的費(fèi)用

設(shè)對(duì)于可行流f 存在可擴(kuò)充鏈P，當(dāng)以ε=1 調(diào)整f 而得到可行流f' 時(shí)，兩流的費(fèi)用之差成為可擴(kuò)充鏈p 的費(fèi)用。其中P 和P- 分別表示p 上的前向弧和后向弧。

最小費(fèi)用最大流問題是經(jīng)濟(jì)學(xué)和管理學(xué)中的一類典型問題。在一個(gè)網(wǎng)絡(luò)中每段路徑都有“容量”和“費(fèi)用”兩個(gè)限制的條件下，此類問題的研究試圖尋找出：流量從A到B，如何選擇路徑、分配經(jīng)過路徑的流量，可以達(dá)到所用的費(fèi)用最小的要求。

在實(shí)際中：n輛卡車要運(yùn)送物品，從A地到B地。由于每條路段都有不同的路費(fèi)要繳納，每條路能容納的車的數(shù)量有限制，如何分配卡車的出發(fā)路徑可以達(dá)到費(fèi)用最低，物品又能全部送到。

在圖論中，網(wǎng)絡(luò)流（英語：Network flow）是指在一個(gè)每條邊都有容量（capacity）的有向圖分配流，使一條邊的流量不會(huì)超過它的容量。通常在運(yùn)籌學(xué)中，有向圖稱為網(wǎng)絡(luò)。頂點(diǎn)稱為節(jié)點(diǎn)（node）而邊稱為弧（arc）。一道流必須匹配一個(gè)結(jié)點(diǎn)的進(jìn)出的流量相同的限制，除非這是一個(gè)源點(diǎn)（source）──有較多向外的流，或是一個(gè)匯點(diǎn)（sink）──有較多向內(nèi)的流。一個(gè)網(wǎng)絡(luò)可以用來模擬道路系統(tǒng)的交通量、管中的液體、電路中的電流或類似一些東西在一個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)中游動(dòng)的任何事物。

由割集的定義不難看出，無論拿掉那個(gè)割集，發(fā)點(diǎn)v_s到收點(diǎn)v_t便不再相通，所以任何一個(gè)可行流都會(huì)經(jīng)過割集，且不會(huì)超過任一割集的容量。最小割如同瓶頸一般，即使是最大流也無法超過最小割，網(wǎng)絡(luò)的最大流與最小割容量滿足下面的定理（證明略）。

最大流問題定理一

設(shè)f為網(wǎng)絡(luò)G=(V,E,C)的任一可行流，流量為v(f)，

最大流問題定理二

由定理一可知，最大流的流量v(f)和某一割集K的容量相等，而且最大流的流量本身也不帶任一割集的容量，因此割集一定是最小的割集。

任一網(wǎng)絡(luò)G中，從v_s到v_t的最大流的流量等于分離v_s、v_t的最小割的容量（最小的割集的容量）。

最大流問題前后向弧

一條從起點(diǎn)v_s到終點(diǎn)vt的鏈μ，規(guī)定從v_s到v_t的方向?yàn)殒湨痰姆较?，鏈上與μ方向一致的邊叫前向?。ㄟ叄?，記作μ^-；與μ方向相反的邊稱為后向?。ㄟ叄?，記作μ 。

最大流問題可增廣鏈

f是一個(gè)可行流，f_ij表示由i點(diǎn)指向j點(diǎn)的流量，如果滿足前向弧的流量非負(fù)且小于容量，或后向弧的流量大于0且不超過容量：

則稱μ為從v_s到v_t的關(guān)于f的可增廣鏈。

可增廣鏈的實(shí)際意義是：沿著這條從v_s到v_t輸送的流，仍有潛力可挖，只要前向弧的流量增加或后向弧的流量減少，就可以將截集的流量提高。調(diào)整后的流，在各點(diǎn)仍滿足平衡條件及容量限制條件，仍為可行流。

從另一個(gè)角度來說，可以提高流量的可行流也不是最大流，因此可行流f是最大流的充要條件是不存在從v_s到v_t的可增廣鏈。