【正文】 步驟 2： 沿找到的最小費用可增廣路增流，并轉(zhuǎn)步驟 1。 ?????????PwvvwtPwvwvtwvwt),(),(c o s),(),(c o s),(2021年 11月 12日 59 最小費用路算法 ?求最小費用流的最小費用路算法步驟： 步驟 0： 初始可行 0流。 ?殘流網(wǎng)絡中從源 s到匯 t的最小費用路是殘流網(wǎng)絡中從 s到 t的以費用為權的最短路。 2021年 11月 12日 57 最小費用路算法 ?最小費用路算法類似于求最大流的增廣路算法的思想。如果不存在負費用圈，則計算結束，已經(jīng)找到最小費用流。 ?最小費用流問題的最優(yōu)性條件： 網(wǎng)絡 G的最大流 flow是 G的一個最小費用流的充分且必要條件是 flow所相應的殘流網(wǎng)絡中沒有負費用圈。 ?增大回路中剩余容量的定義與殘流網(wǎng)絡中剩余容量的定義一致；其上代價或費用定義為 p中前向邊上的費用之和減去 p中后向邊上的費用之和，用 w(p)表示。 ????Ewvwvf l o wwvtf l o wt),(),(),(c o s)(c o s2021年 11月 12日 54 消圈算法 ?基本思想：首先找到網(wǎng)絡中的一個最大流，然后通過消去負費用圈使費用降低。 2021年 11月 12日 52 提綱 一、線性規(guī)劃問題和單純形算法 二、最大網(wǎng)絡流問題 三、最小費用流問題 2021年 11月 12日 53 問題描述 ?網(wǎng)絡流的費用 ?對于網(wǎng)絡的每一條邊 (v,w) ，定義一個單位流量費用cost(v,w)。在從 X指向 Y的邊集中，流量為 1的邊對應于二分圖中的匹配邊。 （ 4）臵 F中所有邊的容量都為 1。 （ 2）把 G中的每一條邊添加到 F中，但是使得邊的方向從 X中的頂點指向 Y中的頂點。如下構造一個流網(wǎng)絡 F，使得 F中的一個最大流可以直接轉(zhuǎn)換為 G中的一個最大匹配。 ?二分圖的最大匹配問題就是在已知圖 G是一個二分圖的前提下，求 G的最大匹配。如果 M E，且 M中任何兩條邊都不與同一個頂點相關聯(lián)，則稱 M是 G的一個匹配。如果頂點集合 V可分割為兩個互不相交的子集 X和 Y，并且圖中每條邊（ i , j）所關聯(lián)的兩個頂點 i和 j分屬于這兩個不同的頂點集，則稱圖 G為一個二分圖。 ? 新網(wǎng)絡的最大流對應于原網(wǎng)絡的最大流。將多源點多匯點網(wǎng)絡的最大流問題轉(zhuǎn)化為等價的單源單網(wǎng)絡的最大流問題的方法： ? 在原網(wǎng)絡的基礎上，增加一個虛源 s和一個虛匯 t。 ? 在基于頂點的預流推進算法中，選定一個活頂點后，算法沿該活頂點的所有推流邊進行推流運算，直至無可推流邊或該頂點的存流變成 0時為止。 ? 一般的預流推進算法并未給出如何選擇活頂點和可推流邊。 ?? ?? ? EvwEwv vwf lo wwvf lo w ),(),( ),(),(?? ?? ? EvwEwv vwf lo wwvf lo w ),(),( ),(),(?? ?? ? EwvEvw wvf lo wvwf lo w ),(),( ),(),(2021年 11月 12日 48 預流推進算法 ? 如果當前活頂點有多個鄰點，那么首先推進到哪個鄰點呢 ? ? 由于算法最后的目的是盡可能將流推進到匯點 t，因此算法應尋求把流量推進到它的鄰點中距頂點 t最近的頂點。 ? 對網(wǎng)絡 G上的一個預流，如果存在活頂點，則說明該預流不是可行流。 ?即對每個 v∈ V(v≠s,t)有 ? 滿足條件 的中間頂點 v稱為 活頂點 。 ?該函數(shù)滿足容量約束，即對 G的每一條邊 (v,w)∈ E，滿足0≤flow(v,w)≤cap(v,w)。這種流稱為預流（ preflow）。 2021年 11月 12日 46 預流推進算法 ? 在算法的推進過程中，網(wǎng)絡流滿足容量約束，但一般不滿足流量平衡約束。 ? 預流推進算法注重對每一條邊的增流，而不必每次一定對一條增廣路增流。 if (v,w) ∈ p then f[v,w]=f[v,w]d。 } While there exists a path p from s to t in the residual work Gf {do: d=min{△ f(v,w): (v,w) is in p}。 2021年 11月 12日 44 FORDFULKERSON(G,s,t) For each edge(v,w) ∈ E(G) {do: f[v,w]=0。也就是殘流網(wǎng)絡中 P的最大容量。 ? 按照這個原則， d既不能超過每條向前邊 (v,w)的 cap(v,w)flow(v,w)，也不能超過每條向后邊 (v,w)的 flow(v,w)。 2021年 11月 12日 42 增廣路算法 具體做法是： （ 1）不屬于可增廣路 P的邊 (v,w)上的流量保持不變； （ 2）可增廣路 P上的所有邊 (v,w)上的流量按下述規(guī)則變化：在向前邊 (v,w)上， flow(v,w)+d；在向后邊 (v,w)上，flow(v,w)d。 則稱 P為關于可行流 flow的一條可增廣路。向后邊的全體記為 P。向前邊的全體記為 P+。定義路的方向是從 s到 t。 ? 當 flow(v,w)＝ cap(v,w)時，殘流網(wǎng)絡 G*中有唯一的一條邊 (w,v)與之對應，且該邊的容量為 cap(v,w)。 ? 當 flow(v,w)cap(v,w)時， (v,w)是 G*中的一條邊，該邊的容量為cap*(v,w)=cap(v,w)flow(v,w)。對于網(wǎng)絡中一個給定的流 flow，其費用定義為： ????Ewvwvf l o wwvtf l o wt),(),(),(c o s)(c o s2021年 11月 12日 40 ?殘流網(wǎng)絡 ? 網(wǎng)絡 G關于流 flow的殘流網(wǎng)絡 G*與 G有相同的頂點集 V，而網(wǎng)絡 G中的每一條邊對應于 G*中的 1條邊或 2條邊。 ?最大流 ?最大流問題即求網(wǎng)絡 G的一個可行流 flow，使其流量 f達到最大。 基本概念和術語 2021年 11月 12日 38 ?邊流 ?對于網(wǎng)絡 G的一個給定的可行流 flow，將網(wǎng)絡中滿足flow(v,w)=cap(v,w)的邊稱為 飽和邊 ； flow(v,w)cap(v,w)的邊稱為 非飽和邊 ； flow(v,w)=0的邊稱為 零流邊 ； flow(v,w)0的邊稱為 非零流邊 。 ?可行流總是存在的。 ?對于匯 t： t的流入量－ t的流出量的 =匯的凈輸入量 f。即對每個