最小費用最大流

前向弧和後向弧

在網絡D(V,A) 中,如果對連接發點vs和收點vt 的一條鏈P，方向規定為從vs 到vt，則當鏈P 中弧(vi,vj)

的方向與規定的方向一致時，稱弧（vi,vj) 為前向弧，否則稱為後向弧。不在這條鏈上的弧，不定義前向弧和後向弧。

可擴充鏈

設{fij}為一可行流（假設為非負值），如果存在從發點vs 到收點vt 的鏈P，在鏈P 上，下列兩條同時滿足，則稱P 為可擴充鏈：

①對於P 上的前向弧（vi,vj) 有fij

②對於P 上的後向弧（vi,vj) 有fij>0。

可擴充鏈P的費用

設對於可行流f 存在可擴充鏈P，當以ε=1 調整f 而得到可行流f' 時，兩流的費用之差成為可擴充鏈p 的費用。其中P+和P- 分別表示p 上的前向弧和後向弧。

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

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

由於第二種算法和已介紹的最大流算法接近，且算法中尋找最小費用增流鏈，可以轉化為一個尋求源點至匯點的最短路徑問題，所以這裏介紹這一算法。

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

計算中有一個問題需要解決。這就是增流網絡G ′中有負權邊，因而不能直接應用標號法來尋找x至y的最短路徑，採用其它計算有負權邊的網絡最短路徑的方法來尋找x至y的最短路徑，將 大大降低計算效率。為了仍然採用標號法計算最短路徑，在每次建立增流網絡求得最短路徑後，可將網絡G的權w(e）做一次修正，使再建的增流網絡不會出現負權邊，並保證最短路徑不至於因此而改變。下面介紹這種修改方法。當流值為零，第一次建增流網絡求最短路徑時，因無負權邊，當然可以採用標號法進行計算。為了使以後建立增流網絡時不出現負權邊，採取的辦法是將 G中有流邊（f(e)>0）的權w(e）修正為0。為此， 每次在增流網絡上求得最短路徑後，以下式計算G中新的邊權w " (u,v）：

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

式中 L(u),L(v) -- 計算G′的x至y最短路徑時u和v的標號值。第一次求最短徑時如果（u,v）是增流路徑上的邊， 則據最短 路徑算法一定有 L(v)=L(u)+w &apos; (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）後，對任一邊，皆有w(e）≥0， 且有流 的邊（增流鏈上的邊），一定有w(e)=0。以後每次迭代計算，若 f(u,v)>0，增流網絡需建立（v,u）邊，邊權數w &apos; (v,u)=-w(u,v) =0，即不會再出現負權邊。 此外，每次迭代計算用（*）式修正一切w(e）， 不難證明對每一條x至y的路徑而言，其路徑長度都同樣增加L(x)-L(y）。因此，x至y的最短路徑不會因對w(e）的修正而發生變化。

【計算步驟】

⒈ 對網絡G=[V,E,C,W]，給出流值為零的初始流。

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

⒊ 若G′不存在x至y的路徑，則G的流即為最小費用最大流， 停止計算；否則用標號法找出x至y的最短路徑P。

⒋ 根據P，在G上增流：對P的每條邊（u,v），若G存在（u,v），則（u,v）增流；若G存在（v,u），則（v,u）減流。增（減）流後，應保證對任一邊有c(e）≥ f(e）≥0。

⒌ 根據計算最短路徑時的各頂點的標號值L(v），按下式修 改G一切邊的權數w(e):

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

⒍ 將新流視為初始流，轉2。

augmentpath

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

原有網絡為G，設有一輔助圖G&apos;，其定義為V(G&apos;) = V(G），E(G&apos;）初始值（也就是容量）與E(G）相同。每次操作時從Source點搜索出一條到Sink點的路徑，然後將該路徑上所有的容量減去該路徑上容量的最小值，然後對路徑上每一條邊；添加或擴大反方向的容量，大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。

我們很容易覺得這個算法會陷入死循環，但事實上不是這樣的。我們只需要注意到每次網絡中由Source到Sink的流都增加了，若容量都是整數，則這個算法必然會結束。

尋找通路的時候可以用DFS，BFS最短路等算法。就這兩者來説，BFS要比DFS快得多，但是編碼量也會相應上增加。

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

pushlabel

譯為“預流推進”算法。

可以想象在一個自來水管網的源頭儘可能多的注入水流之後，最多有多少水可以流到匯點去，由網絡的各個節點和管道來約束流量。將每個節點都看成一個水站，他的通過能力是有限的不能通過的水只能退回去。

Push-Relabel

譯為壓入與重標記算法

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

Relabel-to-Front使用一個鏈表保存溢出頂點，用Discharge操作不斷使溢出頂點不再溢出。

Discharge的操作過程是：若找不到可被壓入的臨邊，則重標記，否則對臨邊壓入，直至點不再溢出。

算法的主過程是：首先將源點出發的所有邊充滿，然後將除源和匯外的所有頂點保存在一個鏈表裏，從鏈表頭開始進行Discharge，如果完成後頂點的高度有所增加，則將這個頂點置於鏈表的頭部，對下一個頂點開始Discharge。

Relabel-to-Front算法的時間複雜度是O(V^3），還有一個叫Highest Label Preflow Push的算法複雜度據説是O(V^2*E^0.5）。我研究了一下HLPP，感覺它和Relabel-to-Front本質上沒有區別，因為Relabel-to-Front每次前移的都是高度最高的頂點，所以也相當於每次選擇最高的標號進行更新。還有一個感覺也會很好實現的算法是使用隊列維護溢出頂點，每次對pop出來的頂點discharge，出現了新的溢出頂點時入隊。

Push-Relabel類的算法有一個名為gap heuristic的優化，就是當存在一個整數0k的頂點v做更新，若它小於V+1就置為V+1。

c++程序舉例

typedef pair<int,int> P;

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

int V;

vector<edge> 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<P,vector<P>,greater<P> > 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]<p.first) continue;

for(int i=0;i<G[v].size();i++) {

edge &e=G[v][i];

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<V;v++) h[v]+=dist[v];

int d=f;

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;

}