Ford-Fulkerson演算法

習題預習

1. 你有一個有向圖形，每條邊都有一個正整數的容量。從頂點s開始，到頂點t結束。求從s到t的最大流。

2. 給定一個二分圖，以及源點s和匯點t，請計算最大流值。

3. 在一個有向圖形中，每個邊都有一個正的權值，求最大權重匹配。

4. 假設你有一個實時網路，將每個節點表示為一個點。s表示源點，t表示匯點，每條邊都有一個流速。現在，一個節點被標記為黑色，意味著它的能力提高了。該算法如何計算新的最大流？

5. 在一個有向圖形中，每條邊都有一個正整數的容量和成本。求從s到t的最小花費流。

說明知識

Ford-Fulkerson演算法（Ford-Fulkerson Algorithm）是一種解決最大流問題（Max Flow Problem）的基本算法，通常用於網路流（Network Flow）研究中。

該演算法的核心思想是在網路中尋找增廣路（augmenting path），並利用增廣路來增加最大流量（Max Flow）。增廣路是指從源節點到匯點之間存在一條路徑，路徑上還有可用的流量，通過增加這些路徑上的流量可以得到更大的最大流。

該算法的步驟如下：

1.初始化最大流等於0。

2.在圖中尋找增廣路。

3.如果找到增廣路，則通過增加增廣路上的流量來增加最大流，並返回步驟2。

4.如果找不到增廣路，則回傳最大流。

下面以一個簡單的例子說明Ford-Fulkerson演算法的運作過程：

示例圖為一個有向圖，表示一個流網路，S是源點，T是匯點，數字表示邊界的最大流量。我們要求S到T的最大流。

step 1， 最大流等於0。

step 2，尋找增廣路，以S為起點，從1邊增廣，將流量設定為1，網路變成。

step 3，尋找增廣路，以S為起點，從2邊增廣，將流量設定為2，網路變成。

網路中不存在增廣路，因此得到最大流為3。

彙總重點

Ford-Fulkerson算法是一種用於解決最大流問題的經典算法，它的重點可以概括為以下幾點：

1. 確定流量網絡

Ford-Fulkerson算法先將圖形建立為流量網絡，其中包括節點、邊以及對應的容量值。

2. 確定增廣路徑

算法通過尋找增廣路徑來增大網絡流量，增廣路徑是指一條起始節點和終止節點之間，且經過的所有邊上還有剩餘容量的路徑。

3. 確定增廣路徑上的瓶頸容量

增廣路徑上所有邊剩餘容量的最小值即稱為瓶頸容量，該值決定了增廣路徑對網絡流量的貢獻。

4. 通過增益容量調整網絡流量

將增益容量加入增量流，同時從增量容量中減去瓶頸容量，以便在該路徑上繼續尋找更多的瓶頸容量。

5. 重複進行增廣路徑搜索直到不存在增廣路徑為止

不斷尋找增廣路徑並調整流量直到無法找到增廣路徑，此時網絡流量即達到了最大值。

總體而言，Ford-Fulkerson算法的關鍵在於如何尋找增廣路徑，並且在其中找到可以增大網絡流量的最小瓶頸容量。該算法的時間複雜度為O(Ef)，其中E表示網絡流量總邊數，f表示最大流量值。

知識測驗

1. 在下圖中，使用Ford-Fulkerson演算法找到將從節點S到節點T的最大流。在創建殘留圖時，先從所有容量為0的反向邊開始，創建具有最下容量的邊。

答案：最大流為23

2. 在下圖中，使用Ford-Fulkerson演算法找到將從節點A到節點F的最大流。

答案：最大流為4

3. 在下圖中，使用Ford-Fulkerson演算法找到將從節點S到節點T的最大流。

答案：最大流為14

4. 在下圖中，使用Ford-Fulkerson演算法找到將從節點A到節點D的最大流。

答案：最大流為10

5. 在下圖中，使用Ford-Fulkerson演算法找到將從節點S到節點T的最大流。

答案：最大流為23