最小費用路算法java（過路費算法）

本文目錄一覽：

• 1、java 最短路徑算法 如何實現有向 任意兩點的最短路徑
• 2、有什麼無權無向圖的最短路徑算法比較好，求一個用java實現的
• 3、最小費用流和最小費用最大流有什麼區別？
• 4、網絡流的最小費用流算法
• 5、求最短路徑算法

java 最短路徑算法 如何實現有向 任意兩點的最短路徑

Dijkstra(迪傑斯特拉)算法是典型的最短路徑路由算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式

用OPEN,CLOSE表的方式，其採用的是貪心法的算法策略，大概過程如下：

1.聲明兩個集合，open和close，open用於存儲未遍歷的節點，close用來存儲已遍歷的節點

2.初始階段，將初始節點放入close，其他所有節點放入open

3.以初始節點為中心向外一層層遍歷，獲取離指定節點最近的子節點放入close並從新計算路徑，直至close包含所有子節點

代碼實例如下：

Node對象用於封裝節點信息，包括名字和子節點

[java] view plain copy

public class Node {

private String name;

private MapNode,Integer child=new HashMapNode,Integer();

public Node(String name){

this.name=name;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public MapNode, Integer getChild() {

return child;

}

public void setChild(MapNode, Integer child) {

this.child = child;

}

}

MapBuilder用於初始化數據源，返回圖的起始節點

[java] view plain copy

public class MapBuilder {

public Node build(SetNode open, SetNode close){

Node nodeA=new Node(“A”);

Node nodeB=new Node(“B”);

Node nodeC=new Node(“C”);

Node nodeD=new Node(“D”);

Node nodeE=new Node(“E”);

Node nodeF=new Node(“F”);

Node nodeG=new Node(“G”);

Node nodeH=new Node(“H”);

nodeA.getChild().put(nodeB, 1);

nodeA.getChild().put(nodeC, 1);

nodeA.getChild().put(nodeD, 4);

nodeA.getChild().put(nodeG, 5);

nodeA.getChild().put(nodeF, 2);

nodeB.getChild().put(nodeA, 1);

nodeB.getChild().put(nodeF, 2);

nodeB.getChild().put(nodeH, 4);

nodeC.getChild().put(nodeA, 1);

nodeC.getChild().put(nodeG, 3);

nodeD.getChild().put(nodeA, 4);

nodeD.getChild().put(nodeE, 1);

nodeE.getChild().put(nodeD, 1);

nodeE.getChild().put(nodeF, 1);

nodeF.getChild().put(nodeE, 1);

nodeF.getChild().put(nodeB, 2);

nodeF.getChild().put(nodeA, 2);

nodeG.getChild().put(nodeC, 3);

nodeG.getChild().put(nodeA, 5);

nodeG.getChild().put(nodeH, 1);

nodeH.getChild().put(nodeB, 4);

nodeH.getChild().put(nodeG, 1);

open.add(nodeB);

open.add(nodeC);

open.add(nodeD);

open.add(nodeE);

open.add(nodeF);

open.add(nodeG);

open.add(nodeH);

close.add(nodeA);

return nodeA;

}

}

圖的結構如下圖所示：

Dijkstra對象用於計算起始節點到所有其他節點的最短路徑

[java] view plain copy

public class Dijkstra {

SetNode open=new HashSetNode();

SetNode close=new HashSetNode();

MapString,Integer path=new HashMapString,Integer();//封裝路徑距離

MapString,String pathInfo=new HashMapString,String();//封裝路徑信息

public Node init(){

//初始路徑,因沒有A-E這條路徑,所以path(E)設置為Integer.MAX_VALUE

path.put(“B”, 1);

pathInfo.put(“B”, “A-B”);

path.put(“C”, 1);

pathInfo.put(“C”, “A-C”);

path.put(“D”, 4);

pathInfo.put(“D”, “A-D”);

path.put(“E”, Integer.MAX_VALUE);

pathInfo.put(“E”, “A”);

path.put(“F”, 2);

pathInfo.put(“F”, “A-F”);

path.put(“G”, 5);

pathInfo.put(“G”, “A-G”);

path.put(“H”, Integer.MAX_VALUE);

pathInfo.put(“H”, “A”);

//將初始節點放入close,其他節點放入open

Node start=new MapBuilder().build(open,close);

return start;

}

public void computePath(Node start){

Node nearest=getShortestPath(start);//取距離start節點最近的子節點,放入close

if(nearest==null){

return;

}

close.add(nearest);

open.remove(nearest);

MapNode,Integer childs=nearest.getChild();

for(Node child:childs.keySet()){

if(open.contains(child)){//如果子節點在open中

Integer newCompute=path.get(nearest.getName())+childs.get(child);

if(path.get(child.getName())newCompute){//之前設置的距離大於新計算出來的距離

path.put(child.getName(), newCompute);

pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+”-“+child.getName());

}

}

}

computePath(start);//重複執行自己,確保所有子節點被遍歷

computePath(nearest);//向外一層層遞歸,直至所有頂點被遍歷

}

public void printPathInfo(){

SetMap.EntryString, String pathInfos=pathInfo.entrySet();

for(Map.EntryString, String pathInfo:pathInfos){

System.out.println(pathInfo.getKey()+”:”+pathInfo.getValue());

}

}

/**

* 獲取與node最近的子節點

*/

private Node getShortestPath(Node node){

Node res=null;

int minDis=Integer.MAX_VALUE;

MapNode,Integer childs=node.getChild();

for(Node child:childs.keySet()){

if(open.contains(child)){

int distance=childs.get(child);

if(distanceminDis){

minDis=distance;

res=child;

}

}

}

return res;

}

}

Main用於測試Dijkstra對象

[java] view plain copy

public class Main {

public static void main(String[] args) {

Dijkstra test=new Dijkstra();

Node start=test.init();

test.computePath(start);

test.printPathInfo();

}

}

有什麼無權無向圖的最短路徑算法比較好，求一個用java實現的

有什麼無權無向圖的最短路徑算法比較好

帶權圖也分有向和無向兩種，基本的算法可以看看書咯。 帶權的無向圖的最短路徑又叫最小生成樹，Prim算法和Kruskal算法； 帶權的有向圖的最短路徑算法有迪傑斯特拉算法和佛洛依德算法；

String[] s={“January”, “February”, “March”, “April”, “May”, “June”, “July”, “August”, “September”, “October”, “November”, “December”};

System.out.print(“請輸入數字（1-12）：”);

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

String str=br.readLine();

int m=Integer.parseInt(str);

if (m=0||m=13)

{

最小費用流和最小費用最大流有什麼區別？

最小費用最大流是指：滿足最大流的情況下，讓費用最小。

最小費用流：僅要求費用最小，通常情況下有費用為負的邊權(如果費用全為正，那麼可以讓流量為0，費用也就是0)，可以使用最小費用最大流的算法求解，只不過終止條件變為“從原點到匯點的費用為正”

最小費用最大流算法的原本終止條件為“從原點到匯點的容量為0”

網絡流的最小費用流算法

一．Ford和Fulkerson迭加算法.

基本思路：把各條弧上單位流量的費用看成某種長度,用求解最短路問題的方法確定一條自V1至Vn的最短路;在將這條最短路作為可擴充路,用求解最大流問題的方法將其上的流量增至最大可能值;而這條最短路上的流量增加後,其上各條弧的單位流量的費用要重新確定,如此多次迭代,最終得到最小費用最大流.

迭加算法：

1) 給定目標流量F或∞,給定最小費用的初始可行流=0

2) 若V(f)=F,停止,f為最小費用流;否則轉(3).

3) 構造 相應的新的費用有向圖W(fij),在W(fij)尋找Vs到Vt的最小費用有向路P(最短路),沿P增加流f的流量直到F,轉(2);若不存在從Vs到Vt的最小費用的有向路P,停止.f就是最小費用最大流.

具體解題步驟：

設圖中雙線所示路徑為最短路徑，費用有向圖為W（fij）．

在圖(a)中給出零流 f,在圖(b)中找到最小費用有向路,修改圖(a)中的可行流,δ=min{4,3,5}=3,得圖(c),再做出(c)的調整容量圖,再構造相應的新的最小費用有向路得圖(d), 修改圖(c)中的可行流, δ=min{1,1,2,2}=1,得圖(e),以此類推,一直得到圖(h),在圖(h)中以無最小費用有向路,停止,經計算:

圖(h)中 最小費用=1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38

圖(g)中 最大流=5

最大流問題僅注意網絡流的流通能力，沒有考慮流通的費用。實際上費用因素是很重要的。例如在交通運輸問題中，往往要求在完成運輸任務的前提下，尋求一個使總運輸費用最省的運輸方案，這就是最小費用流問題。如果只考慮單位貨物的運輸費用，那麼這個問題就變成最短路問題。由此可見，最短路問題是最小費用流問題的基礎。現已有一系列求最短路的成功方法。最小費用流(或最小費用最大流)問題 ，可以交替使用求解最大流和最短路兩種方法，通過迭代得到解決。

二．圈算法：

1) 利用Ford和Fulkson標號算法找出流量為F(=最大流)的流f.

2) 構造f對應的調整容量的流網絡N'(f).

3) 搜索N'(f)中的負費用有向圖C(Floyd算法),若沒有則停止,否則轉(4).

4) 在C上找出最大的循環流,並加到N上去,同時修改N'(F)中C的容量,轉(3).

三，ZKW費用流

費用流是網絡流的一個很重要的組成部分，也是非常有用的一種圖論模型，關於費用流的算法，流傳比較廣的主要是消圈和增廣路算法，而近來炒得沸沸揚揚的ZKW算法也是一種非常優秀的算法，這裡我就談談我對此算法的一些理解。

此算法是由ZKW大牛創立，主要思想仍然是找增廣路，只是有了一些優化在裡邊。原來我們找增廣路主要是依靠最短路算法，如SPFA。因此此算法的時間複雜度主要就取決於增廣的次數和每次增廣的耗費。由於每一次找增廣路是都是重新算一遍，這樣似乎顯得有些浪費，如果我們能夠縮短找增廣路的時間，那必定會大大地優化算法。

值得注意的是，在尋求最短路得過程中，設dis[i]為i到起點的距離，對於每一條由i引向j的邊，必有dis[j]=dis[i]+map[i][j]；既然滿足這樣的恆等式，我們就可以借用KM算法的調整思想來尋求最短路，每次只走dis[j]=dis[i]+map[i][j]的路徑，一旦不存在到達終點的路徑，就掃描每一條邊，找到最小的距離增加值，使得有至少一條新邊被加入相等子圖。

算法流程如下：

1.將dis數組清零，表示當前的相等子圖內只有起點。

（如果存在負權邊，必須要用spfa跑一遍，初始化出dis數組，下面的第二題就是這樣的例子）。

2.深搜，如果到達終點，全部回退更改流量，再進行步驟2；否則，轉3。

3.修改dis的值，如果無法修改，結束程序，已經找到的答案，反之轉2。

有上下界

v上面討論的網絡流都只對每條弧都限定了上界（其實其下界可以看成0），現在給每條弧Vi, Vj加上一個下界限制Aij (即必須滿足Aij≤fij)。

v弧上數字對第一個是上界，第二個是下界。若是撇開下界不看，此圖的最大流如圖(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了。

網絡算法

一、網絡流的基本概念

先來看一個實例。

現在想將一些物資從S運抵T，必須經過一些中轉站。連接中轉站的是公路，每條公路都有最大運載量。如下圖：

每條弧代表一條公路，弧上的數表示該公路的最大運載量。最多能將多少貨物從S運抵T？

這是一個典型的網絡流模型。為了解答此題，我們先了解網絡流的有關定義和概念。

若有向圖G=(V,E)滿足下列條件：

1、 有且僅有一個頂點S，它的入度為零，即d-(S) = 0，這個頂點S便稱為源點，或稱為發點。

2、 有且僅有一個頂點T，它的出度為零，即d+(T) = 0，這個頂點T便稱為匯點，或稱為收點。

3、 每一條弧都有非負數，叫做該邊的容量。邊(vi, vj)的容量用cij表示。

則稱之為網絡流圖，記為G = (V, E, C)

譬如圖5-1就是一個網絡流圖。

1．可行流

對於網絡流圖G，每一條弧(i,j)都給定一個非負數fij，這一組數滿足下列三條件時稱為這網絡的可行流，用f表示它。

(1) 每一條弧(i,j)有fij≤cij。

(2) 除源點S和匯點T以外的所有的點vi，恆有：

該等式說明中間點vi的流量守恆，輸入與輸出量相等。

(3) 對於源點S和匯點T有：

這裡V(f)表示該可行流f的流量。

例如對圖5-1而言，它的一個可行流如下：

流量V(f) = 5。

2．可改進路

給定一個可行流f=。若fij = cij，稱vi, vj為飽和弧；否則稱vi, vj為非飽和弧。若fij = 0，稱vi, vj為零流弧；否則稱vi, vj為非零流弧。

定義一條道路P，起點是S、終點是T。把P上所有與P方向一致的弧定義為正向弧，正向弧的全體記為P+；把P上所有與P方向相悖的弧定義為反向弧，反向弧的全體記為P-。

譬如在圖5-1中，P = (S, V1, V2, V3, V4, T)，那麼

P+ = {S, V1, V1, V2, V2, V3, V4, T}

P- = {V4, V3}

給定一個可行流f，P是從S到T的一條道路，如果滿足：

那麼就稱P是f的一條可改進路。（有些書上又稱：可增廣軌）之所以稱作“可改進”，是因為可改進路上弧的流量通過一定的規則修改，可以令整個流量放大。具體方法下一節會重點介紹，此不贅述。

3．割切

要解決網絡最大流問題，必須先學習割切的概念和有關知識。

G = (V, E, C)是已知的網絡流圖，設U是V的一個子集，W = V\U，滿足S U，T W。即U、W把V分成兩個不相交的集合，且源點和匯點分屬不同的集合。

對於弧尾在U，弧頭在W的弧所構成的集合稱之為割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，記為C（U，W），即：

例如圖5-1中，令U = {S, V1}，則W = {V2, V3, V4, T}，那麼

C(U, W) = S, V2 + V1, V2 + V1, V3+V1, V4=8+4+4+1=17

定理：對於已知的網絡流圖，設任意一可行流為f，任意一割切為(U, W)，必有：V(f) ≤ C(U, W)。

通俗簡明的講：“最大流小於等於任意割”。這是“流理論”里最基礎最重要的定理。整個“流”的理論系統都是在這個定理上建立起來的，必須特別重視。

下面我們給出證明。

網絡流、可改進路、割切都是基礎的概念，應該紮實掌握。它們三者之間乍一看似乎風馬牛不相干，其實內在聯繫是十分緊密的。

二、求最大流

何謂最大流？首先它必須是一個可行流；其次，它的流量必須達到最大。這樣的流就稱為最大流。譬如對圖5-1而言，它的最大流如下：

下面探討如何求得最大流。

在定義“可改進路”概念時，提到可以通過一定規則修改“可改進路”上弧的流量，可以使得總流量放大。下面我們就具體看一看是什麼“規則”。

對可改進路P上的弧vi, vj，分為兩種情況討論：

第一種情況：vi, vj∈P+，可以令fij增加一個常數delta。必須滿足fij + delta ≤ cij，即delta ≤ cij – fij。

第二種情況：vi, vj∈P-，可以令fij減少一個常數delta。必須滿足fij – delta ≥ 0，即delta ≤ fij

根據以上分析可以得出delta的計算公式：

因為P+的每條弧都是非飽和弧，P-的每條弧都是非零流弧，所以delta 0。

容易證明，按照如此規則修正流量，既可以使所有中間點都滿足“流量守恆”（即輸入量等於輸出量），又可以使得總的流量有所增加（因為delta 0）。

因此我們對於任意的可行流f，只要在f中能找到可改進路，那麼必然可以將f改造成為流量更大的一個可行流。我們要求的是最大流，現在的問題是：倘若在f中找不到可改進路，是不是f就一定是最大流呢？

答案是肯定的。下面我們給出證明。

定理1 可行流f是最大流的充分必要條件是：f中不存在可改進路。

證明：

首先證明必要性：已知最大流f，求證f中不存在可改進路。

若最大流f中存在可改進路P，那麼可以根據一定規則（詳見上文）修改P中弧的流量。可以將f的流量放大，這與f是最大流矛盾。故必要性得證。

再證明充分性：已知流f，並且f中不存在可改進路，求證f是最大流。

我們定義頂點集合U, W如下：

（a） S∈U，

（b） 若x∈U，且fxycxy，則y∈U;

若x∈U，且fyx0，則y∈U。

（這實際上就是可改進路的構造規則）

（c） W = V \ U。

由於f中不存在可改進路，所以T∈W；又S∈U，所以U、W是一個割切（U, W）。

按照U的定義，若x∈U，y∈W，則fxy = cxy。若x∈W，y∈U，則fxy = 0。

所以，

又因 v(f)≤C(U,W)

所以f是最大流。得證。

根據充分性證明中的有關結論，我們可以得到另外一條重要定理：

最大流最小割定理：最大流等於最小割，即max V(f) = min C(U, W)。

至此，我們可以輕鬆設計出求最大流的算法：

step 1. 令所有弧的流量為0，從而構造一個流量為0的可行流f（稱作零流）。

step 2. 若f中找不到可改進路則轉step 5；否則找到任意一條可改進路P。

step 3. 根據P求delta。

step 4. 以delta為改進量，更新可行流f。轉step 2。

step 5. 算法結束。此時的f即為最大流。

三、最小費用最大流

1．問題的模型

流最重要的應用是儘可能多的分流物資，這也就是我們已經研究過的最大流問題。然而實際生活中，最大配置方案肯定不止一種，一旦有了選擇的餘地，費用的因素就自然參與到決策中來。

圖5-8是一個最簡單的例子：弧上標的兩個數字第一個是容量，第二個是費用。這裡的費用是單位流量的花費，譬如fs1=4，所需花費為3*4=12。

容易看出，此圖的最大流（流量是8）為：fs1 = f1t = 5, fs2 = f2t = 3。所以它的費用是：3*5+4*5+7*3+2*3 = 62。

一般的，設有帶費用的網絡流圖G = (V, E, C, W)，每條弧Vi, Vj對應兩個非負整數Cij、Wij，表示該弧的容量和費用。若流f滿足：

(a) 流量V(f)最大。

(b) 滿足a的前提下，流的費用Cost(f) = 最小。

就稱f是網絡流圖G的最小費用最大流。

2．算法設計

我們模仿求最大流的算法，找可改進路來求最小費用最大流。

設P是流f的可改進路，定義 為P的費用（為什麼如此定義？）。如果P是關於f的可改進路中費用最小的，就稱P是f的最小費用可改進路。

求最小費用最大流的基本思想是貪心法。即：對於流f，每次選擇最小費用可改進路進行改進，直到不存在可改進路為止。這樣的得到的最大流必然是費用最小的。

算法可描述為：

step 1. 令f為零流。

step 2. 若無可改進路，轉step 5；否則找到最小費用可改進路，設為P。

step 3. 根據P求delta（改進量）。

step 4. 放大f。轉step 2。

step 5. 算法結束。此時的f即最小費用最大流。

至於算法的正確性，可以從理論上證明。讀者可自己思考或查閱有關運籌學資料。

2．最小費用可改進路的求解

求“最小費用可改進路”是求最小費用最大流算法的關鍵之所在，下面我們探討求解的方法。

設帶費用的網絡流圖G = (V, E, C, W)，它的一個可行流是f。我們構造帶權有向圖B = (V’, E’)，其中：

1、 V’ = V。

2、 若Vi, Vj∈E，fijCij，那麼Vi, Vj∈E’，權為Wij。

若Vi, Vj∈E，fij0，那麼Vj, Vi∈E’，權為-Wij。

顯然，B中從S到T的每一條道路都對應關於f的一條可改進路；反之，關於f的每條可改進路也能對應B中從S到T的一條路徑。即兩者存在一一映射的邏輯關係。

故若B中不存在從S到T的路徑，則f必然沒有可改進路；不然，B中從S到T的最短路徑即為f的最小費用可改進路。

現在的問題變成：給定帶權有向圖B = (V’, E’)，求從S到T的一條最短路徑。

考慮到圖中存在權值為負數的弧，不能採用Dijkstra算法；Floyd算法的效率又不盡如人意——所以，這裡採用一種折衷的算法：迭代法。

設Short[k]表示從S到k頂點的最短路徑長度；從S到頂點k的最短路徑中，頂點k的前趨記為Last[k]。那麼迭代算法描述如下：（為了便於描述，令n = |V’|，S的編號為0，T的編號為n+1）

step 1. 令Short[k]  +∞（1≤k≤n+1），Short[0]  0。

step 2. 遍歷每一條弧Vk, Vj。若Short[k] + k, j Short[j]，則令Short[j]  Short[k] + k, j，同時Last[j]  k。倘不存在任何一條弧滿足此條件則轉step 4。

step 3. 轉step 2.

step 4. 算法結束。若Short[n + 1]= +∞，則不存在從S到T的路徑；否則可以根據Last記錄的有關信息得到最短路徑。

一次迭代算法的時間複雜度為O(kn2)，其中k是一個不大於n的變量。在費用流的求解過程中，k大部分情況下都遠小於n。

3．思維發散與探索

1）可改進路費用：“遞增！遞增？”

設f從零流到最大流共被改進了k次，每i次選擇的可改進路的費用為pi，那麼會不會有p1≤p2≤p3≤……≤pk呢？

2）迭代法：“小心死循環！嘿嘿……”

迭代法會出現死循環嗎？也就是說，構造的帶權有向圖B中會存在負迴路嗎？

3）費用：“你在乎我是負數嗎？”

網絡流圖中的費用可以小於零嗎？

4）容量：“我管的可不僅是弧。”

網絡流圖中的“容量”都是對弧而言的，但若是給每個頂點也加上一個容量限制：即通過此頂點的流量的上限；任務仍然是求從S到T的最小費用最大流。你能解決嗎？

4．C++代碼實現 #includecstdio#includecstring#includealgorithm#includequeueusingnamespacestd;intH[105],X[40005],P[40005],from[40005],flow[40005],cost[40005],tot;inlinevoidadd(intx,inty,intz,intk){P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;from[tot]=x;cost[tot]=k;}intf,c;intn,m;intS,T;intd[105],a[105],p[105];structN{intx,w;friendbooloperator(Na,Nb){returna.wb.w;}N(inta=0,intb=0){x=a,w=b;}};priority_queueNq;boolspfa(){memset(d,0x3f,sizeof(d));d[S]=0;a[S]=inf;p[S]=0;intx;q.push(N(S,0));while(!q.empty()){x=q.top().x;q.pop();if(x==T)continue;for(inti=H[x];i;i=X[i]){if(flow[i]0d[P[i]]d[x]+cost[i]){d[P[i]]=d[x]+cost[i];a[P[i]]=min(a[x],flow[i]);p[P[i]]=i;q.push(N(P[i],d[P[i]]));}}while(!q.empty()d[q.top().x]!=q.top().w)q.pop();}if(d[T]==inf)return0;f+=a[T];c+=a[T]*d[T];x=T;while(x!=S){flow[p[x]]-=a[T];flow[p[x]^1]+=a[T];x=from[p[x]];}return1;}intmain(){#ifdefLOCALfreopen(in.txt,r,stdin);freopen(out.txt,w,stdout);#endifInput();while(spfa());maxflow=f,mincost=c;return0;}四、有上下界的最大流

上面討論的網絡流都只對每條弧都限定了上界（其實其下界可以看成0），現在給每條弧Vi, Vj加上一個下界限制Aij（即必須滿足Aij≤fij）。

例如圖5-9：

弧上數字對第一個是上界，第二個是下界。若是撇開下界不看，此圖的最大流如圖5-10(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了，具體方案見圖5-10(b)。

那麼有上下界的網絡最大流怎麼求呢？

一種自然的想法是去掉下界，將其轉化為只含上界的網絡流圖。這種美好的願望是可以實現的。具體方法如下：

設原網絡流圖為G = (V, E, C, A)，構造不含下界的網絡流圖G’ = (V’, E’, C’)：

1、 V’ = V∪{S’, T’}

2、 對每個頂點x，令 ，若h-(x)≠0，就添加一條弧S’, x，其上界為h-(x)。

3、 對每個頂點x，令 ，若h+(x)≠0，就添加一條弧x, T’，其上界為h+(x)。

4、 對於任何Vi, Vj∈E，都有Vi, Vj∈E’，其上界C’ij = Cij – Aij。

5、 新增T, S∈E’，其上界CTS = +∞。

在G’中以S’為源點、T’為匯點求得最大流f’。若f’中從S’發出的任意一條弧是非飽和弧，則原網絡流圖沒有可行流。否則可得原圖的一個可行流f = f’ + A，即所有的fij = f’ij + Aij。（其正確性很容易證明，留給讀者完成）

然後再求可改進路（反向弧Vi, Vj必須滿足fij≥Aij，而非fij≥0），不斷放大f，直到求出最大流。

我們看到，上幾節所討論的一種可行網絡流實際上是{Aij = 0}的一種特殊網絡流，這裡提出的模型更一般化了。解決一般化的複雜問題，我們採取的思路是將其轉化為特殊的簡單問題，加以研究、推廣，進而解決。這是一種重要的基本思想：化歸——簡單有效。基於這種思想，請讀者自行思考解決：

1、 有上下界的最小流。

2、 有上下界的最小費用最大流。

五、多源點、多匯點的最大流

已知網絡流圖有n個源點S1、S2、……、Sn，m個匯點T1、T2、……、Tm，，求該圖的最大流。這樣的問題稱為多源點、多匯點最大流。

它的解決很簡單：

1、 增設一個“超級源”S’，對每個源點Si，新增弧S’, Si，容量為無窮大。

2、 增設一個“超級匯”T’，對每個匯點Ti，新增弧Ti, T’，容量為無窮大。

3、 以S’為源點、T’為匯點求最大流f。

4、 將f中的S’和T’去掉，即為原圖的最大流。

算法正確性顯然。

六、頂點有容量限制的最大流

上一節已經提出了這個問題，即對於進出每個頂點的流量也規定一個上限，這樣的最大流如何求？

既然我們已經解決了“邊限制”問題，現在何不把“點限制”問題轉化為“邊限制”呢？具體辦法如下：

1、 對除源點和匯點之外的每個頂點i拆分成兩個頂點i’和i’’。新增一條弧i’, i’’，其容量為點i的流量限制。

2、 對於原圖中的弧i, j，我們將其變換成i’’, j’。

3、 對變換後的圖求最大流即可。

這裡我們又一次運用到了化歸的思想：將未知的“點限制”問題轉化為已知的“邊限制”問題。

七、網絡流與二部圖的匹配

{二部圖和匹配的定義可參見本書專門介紹二部圖匹配的章節}

設二部圖為G = (X, Y, E)。

增設點S’，對於所有i∈X，新增弧S’, Xi，容量為1；增設點T’，對於所有i∈Y，新增一條弧Yi, T’，容量也為1。原圖中所有的弧予以保留，容量均為+∞。對新構造出來的網絡流圖以S’為源點、T’為匯點求最大流：流量即為最大匹配數；若弧Xi, Yj（i∈X，j∈Y）的流量非零，它就是一條匹配邊。

二部圖最大匹配問題解決。

那麼二部圖的最佳匹配問題又如何？

仍然按照上述方法構圖。同時令原圖中弧的費用保持不變；新增弧的費用置為0。然後以S’為源點、T’為匯點求最小費用最大流即可。最大流的費用即為原二部圖最佳匹配的費用。

網絡應用

將一連串的水管繪畫成一個網絡。每條水管有一特定的闊度，因此只可以保持一特定的水流量。當任何水管匯合，流入匯流點的總水量必須等於流出的水量，否則我們會很快地缺水，或者我們會團積水。我們有一個作為源點的入水口，和一個作為匯點的出水口。一道流便是一條由源點到匯點而使從出水口流出的總水量一致的可能路徑。直觀地，一個網絡的總流量是水從出口流出的速率。

流可以關於在交通網絡上的人或物質，或電力分配系統上的電力。對於任何這樣的實物網絡，進入任何中途結點的流需要等於離開那結點的流。Bollobás以基爾霍夫電流定律描繪這限制的特性，同時較遲的作者（即 Chartrand）提及它在某些守恆方程的普遍化。

在生態學中也可找到流網絡的應用：當考慮在食物網中不同組織之間養料及能量的流，流網絡便自然地產生。與這些網絡有聯繋的數學問題和那些液體流或交通流網絡中所產生的難題有很大分別。由 Robert Ulanowicz 及其他人發展的生態系統網絡分析領域包含使用信息論及熱力學的概念去研究這些網絡隨時間的演變。

求最短路徑算法

import java.awt.*;

import java.util.HashSet;

import java.util.Random;

class example2 {

    private static Point[] mTestPoints;

    //已知平面上N點坐標,求遍歷所有點的最短路徑.

    public static void main(String[] args) {

        //兩點之間的距離 d=√(a^2+b^2) 其中a=|x1 –x2|;b=|y1 – y2|

        //都是簡單的正相關函數,距離最短那麼需要a+b最小

        //n個點需要求C(n,2)次

        //其實java提供了兩點之間距離的Api咱們直接使用即可

        generateTestPoints();

        double minDistance = Double.MAX_VALUE;

        for (int i = 0; i  mTestPoints.length; i++) {

            //兩兩計算,數組中每個點只跟後面的點求距離

            for (int j = i + 1; j  mTestPoints.length; j++) {

                double distance = mTestPoints[i].distance(mTestPoints[j]);

                if (distance  minDistance) {

                    minDistance = distance;

                }

            }

        }

        //得到結果

        System.out.println(“最短距離為:” + minDistance);

    }

    private static void generateTestPoints() {

        //隨機生成10個點的集合,為了去重使用hashSet

        Random random = new Random();

        HashSetPoint mPointSet = new HashSet();

        for (int i = 0; i  10; i++) {

            boolean add = mPointSet.add(new Point(random.nextInt(100), random.nextInt(100)));

            if (!add) {

                –i;

            }

        }

        mTestPoints = mPointSet.toArray(new Point[10]);

    }

}