Edmonds-Karp演算法

習題預習

1. 假設有一個圖形表示水流網路，每條邊都有一個流量上限。請使用Edmonds-Karp演算法，找出從源頭到匯點的最大流量。
2. 一個國家有很多城市和道路，每條道路都有一個容量限制，請使用Edmonds-Karp演算法找出從一個城市到另一個城市的最大流量。
3. 在一個有向圖中，每條邊都有一個權值，請使用Edmonds-Karp演算法找出從源頭到匯點的最小成本最大流量。
4. 一個城市通往其他城市的交通網路，每條路都有一個容量限制和一個花費，請使用Edmonds-Karp演算法找出從一個城市到另一個城市的最小成本最大流量。
5. 在一個電信網路中，每一條邊都是一條電纜，每個節點都是一個交換機。如果一對交換機之間的電纜故障了，就不能通信。請使用Edmonds-Karp演算法找出一個最小的故障集，使得從源頭到匯點之間的所有交換機都能夠通信。

說明知識

Edmonds-Karp算法是一種用於解決最大流問題的算法，也是尋找最小割的一種有效算法。該算法基於廣度優先搜索的思想，每次選擇最短路徑增廣，用一個附加數組來保留流量以及每個點的前驅節點。

以下是Edmonds-Karp算法的流程：

1. 初始化剩餘網絡：將原始網絡圖轉換成一個容量等同於原圖的剩餘網絡圖。

2. 廣度優先搜索尋找增廣路徑：對剩餘網絡圖進行廣度優先搜索以尋找從源點到決策點的最短路徑，同時標記每個點已訪問。

3. 更新剩餘網絡流量：根據增廣路徑上的最小容量來更新剩餘網絡的流量。

4. 反向增益：回溯增益上的所有邊將流量反轉為反向增量。

5. 重複直到沒有增廣路徑為止。

下面是一個例子：

給定一個5個節點的最大流問題，如下圖所示：

首先，在剩餘網絡中找到一條最短路徑，也就是S到T的路徑。如下圖所示，這條路徑的容量是4。

然後，更新網絡的流量，將上述路徑上的所有邊的流量增加4。如下圖所示：

接下來，找到另一條最短路徑，從S到E到T，容量為3。如下圖所示：

然後更新網絡的流量，將上述路徑上的所有邊的流量增加3。如下圖所示：

繼續用相同的方式尋找增廣路徑，更新網絡流量，直到沒有其他增廣路徑存在為止。

最終得到的最大流量為7，如下圖所示：

彙總重點

1. Edmonds-Karp Algorithm是一種計算最大流量的算法，它是基於Ford-Fulkerson Algorithm的改進版本。
2. 該算法的核心是BFS演算法，用於尋找增廣路。
3. 在每次找到一個增廣路後，該路上的流量被增加，並更新所有經過的邊的殘餘容量。
4. 重複查找增廣路，直到不存在增廣路為止，此時得到的最大流即為最大可行流。
5. 該算法的時間複雜度為O(V*E^2)，其中V是節點數，E是邊數。
6. Edmonds-Karp Algorithm具有良好的可讀性和易實現性，並已被廣泛應用。

知識測驗

1. 在一個網路擁有10個頂點和14條邊的情況下，找出源節點為1，匯點為10時的最大流。

答案：最大流為4。

2. 在一個網路擁有6個頂點和10條邊的情況下，找出源節點為1，匯點為6時的最大流。

答案：最大流為3。

3. 在一個網路擁有8個頂點和12條邊的情況下，找出源節點為1，匯點為8時的最大流。

答案：最大流為5。

4. 在一個網路擁有5個頂點和8條邊的情況下，找出源節點為1，匯點為5時的最大流。

答案：最大流為4。

5. 在一個網路擁有7個頂點和11條邊的情況下，找出源節點為1，匯點為7時的最大流。

答案：最大流為3。