DSA Edmonds-Karp 演算法
Edmonds-Karp 演算法解決了最大流問題。
尋找最大流在許多領域都很有幫助：最佳化網路流量、製造業、供應鏈和物流，或航空公司排程。
Edmonds-Karp 演算法
Edmonds-Karp 演算法解決了有向圖的最大流問題。
流量從源點 (\(s\)) 流出，終止於匯點 (\(t\))，圖中的每條邊都允許一個流量，受容量限制。
Edmonds-Karp 演算法與 Ford-Fulkerson 演算法非常相似，不同之處在於 Edmonds-Karp 演算法使用 廣度優先搜尋 (BFS) 來尋找增廣路徑以增加流量。
最大流：{{maxFlow}}
{{statusText}}Edmonds-Karp 演算法透過使用廣度優先搜尋 (BFS) 找到一條從源點到匯點具有可用容量的路徑（稱為增廣路徑），然後透過該路徑傳送儘可能多的流量。
Edmonds-Karp 演算法會持續尋找新的路徑以傳送更多流量，直到達到最大流量。
在上面的模擬中，Edmonds-Karp 演算法解決了最大流問題：它找出可以從源點 \(s\) 傳送到匯點 \(t\) 的最大流量，該最大流量為 8。
上面模擬中的數字以分數形式書寫，其中第一個數字是流量，第二個數字是容量（該邊的最大可能流量）。因此，例如，邊 \(s \rightarrow v_2\) 上的 0/7 意味著該邊上流量為 0，容量為 7。
您可以在下面看到 Edmonds-Karp 演算法工作原理的基本分步描述，但我們需要稍後深入瞭解更多細節才能真正理解它。
工作原理
- 所有邊的初始流量均為零。
- 使用 BFS 尋找一條可以傳送更多流量的增廣路徑。
- 進行瓶頸計算以找出可以透過該增廣路徑傳送多少流量。
- 增加透過瓶頸計算找到的每條增廣路徑上的流量。
- 重複步驟 2-4，直到找到最大流。當無法再找到新的增廣路徑時，就會發生這種情況。
Edmonds-Karp 中的殘餘網路
Edmonds-Karp 演算法透過建立和使用一種稱為殘餘網路的東西來工作，它是原始圖的表示。
在殘餘網路中，每條邊都具有殘餘容量，即邊的原始容量減去該邊中的流量。殘餘容量可以看作是帶有一定流量的邊中剩餘的容量。
例如，如果邊 \( v_3 \rightarrow v_4 \) 中有 2 單位流量，容量為 3，則該邊的殘餘流量為 1，因為該邊中還有空間可以傳送 1 單位流量。
Edmonds-Karp 中的反向邊
Edmonds-Karp 演算法還使用反向邊來回送流量。這有助於增加總流量。
為了回送流量（與邊的方向相反），為網路中的每條原始邊建立一個反向邊。Edmonds-Karp 演算法然後可以使用這些反向邊以相反方向傳送流量。
反向邊沒有流量或容量，只有殘餘容量。反向邊的殘餘容量總是與相應原始邊中的流量相同。
在我們的例子中，邊 \( v_1 \rightarrow v_3 \) 有 2 單位流量，這意味著相應反向邊 \( v_3 \rightarrow v_1 \) 上有 2 單位殘餘容量。
這僅僅意味著當原始邊 \( v_1 \rightarrow v_3 \) 上有 2 單位流量時，有可能在該邊上回送相同數量的流量，但方向相反。使用反向邊回推流量也可以看作是撤消已經建立的流量的一部分。
具有邊上殘餘容量的殘餘網路的概念，以及反向邊的概念，是 Edmonds-Karp 演算法工作原理的核心，我們將在本頁進一步實現該演算法時詳細討論這一點。
手動演練
圖中最初沒有流量。
Edmonds-Karp 演算法首先使用廣度優先搜尋來尋找可以增加流量的增廣路徑，即 \(s \rightarrow v_1 \rightarrow v_3 \rightarrow t\)。
找到增廣路徑後，進行瓶頸計算以確定可以透過該路徑傳送多少流量，該流量為：2。
因此，在增廣路徑中的每條邊上傳送 2 單位流量。
Edmonds-Karp 演算法的下一次迭代是再次執行這些步驟：找到新的增廣路徑，找出該路徑中的流量可以增加多少，並相應地增加該路徑中邊的流量。
發現下一條增廣路徑是 \(s \rightarrow v_1 \rightarrow v_4 \rightarrow t \)。
此路徑中的流量只能增加 1 單位，因為 \( s \rightarrow v_1 \) 邊中只剩下 1 單位流量的空間。
發現下一條增廣路徑是 \(s \rightarrow v_2 \rightarrow v_4 \rightarrow t\)。
此路徑中的流量可以增加 3 單位。瓶頸（限制邊）是 \( v_2 \rightarrow v_4 \)，因為容量為 3。
找到的最後一條增廣路徑是 \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow t\)。
此路徑中的流量只能增加 2 單位，因為邊 \( v_4 \rightarrow t \) 是此路徑中的瓶頸，只剩下 2 單位流量的空間（\(容量-流量=1\)）。
此時，無法找到新的增廣路徑（無法找到從 \(s\) 到 \(t\) 可以傳送更多流量的路徑），這意味著已找到最大流量，並且 Edmonds-Karp 演算法完成。
最大流量為 8。如上圖所示，從源點 \(s\) 流出的流量 (8) 與流入匯點 \(t\) 的流量相同。
此外，如果您選擇除 \(s\) 或 \(t\) 之外的任何其他頂點，您會發現流入頂點的流量與流出頂點的流量相同。這就是我們所說的流量守恆，這必須適用於所有此類流量網路（每條邊都有流量和容量的有向圖）。
Edmonds-Karp 演算法的實現
為了實現 Edmonds-Karp 演算法，我們建立了一個 Graph 類。
該 Graph 表示具有其頂點和邊的圖
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, c):
self.adj_matrix[u][v] = c
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data第 3 行：我們建立 adj_matrix 來儲存所有邊和邊容量。初始值設定為 0。
第 4 行：size 是圖中頂點的數量。
第 5 行：vertex_data 儲存所有頂點的名稱。
第 7-8 行：add_edge 方法用於新增從頂點 u 到頂點 v 的邊，容量為 c。
第 10-12 行：add_vertex_data 方法用於向圖中新增頂點名稱。頂點索引由 vertex 引數給出，data 是頂點的名稱。
Graph 類還包含 bfs 方法，用於使用廣度優先搜尋查詢增廣路徑
def bfs(self, s, t, parent):
visited = [False] * self.size
queue = [] # Using list as a queue
queue.append(s)
visited[s] = True
while queue:
u = queue.pop(0) # Pop from the start of the list
for ind, val in enumerate(self.adj_matrix[u]):
if not visited[ind] and val > 0:
queue.append(ind)
visited[ind] = True
parent[ind] = u
return visited[t]第 15-18 行：visited 陣列有助於在搜尋增廣路徑時避免重複訪問相同的頂點。queue 儲存待探索的頂點，搜尋總是從源點 s 開始。
第 20-21 行：只要 queue 中有待探索的頂點，就從 queue 中取出第一個頂點，以便可以從那裡找到到下一個頂點的路徑。
第 23 行：對於當前頂點的每個相鄰頂點。
第 24-27 行：如果相鄰頂點尚未被訪問，並且到該頂點的邊上存在殘餘容量：將其新增到待探索的頂點佇列中，標記為已訪問，並將相鄰頂點的 parent 設定為當前頂點 u。
parent 陣列儲存頂點的父節點，從而建立從匯點反向到源點的路徑。parent 稍後在 Edmonds-Karp 演算法中（在 bfs 方法之外）用於增加增廣路徑中的流量。
第 29 行：最後一行返回 visited[t]，如果增廣路徑終止於匯點 t，則該值為 true。返回 true 意味著已找到增廣路徑。
edmonds_karp 方法是我們新增到 Graph 類的最後一個方法
def edmonds_karp(self, source, sink):
parent = [-1] * self.size
max_flow = 0
while self.bfs(source, sink, parent):
path_flow = float("Inf")
s = sink
while(s != source):
path_flow = min(path_flow, self.adj_matrix[parent[s]][s])
s = parent[s]
max_flow += path_flow
v = sink
while(v != source):
u = parent[v]
self.adj_matrix[u][v] -= path_flow
self.adj_matrix[v][u] += path_flow
v = parent[v]
path = []
v = sink
while(v != source):
path.append(v)
v = parent[v]
path.append(source)
path.reverse()
path_names = [self.vertex_data[node] for node in path]
print("Path:", " -> ".join(path_names), ", Flow:", path_flow)
return max_flow最初，parent 陣列包含無效索引值，因為開始時沒有增廣路徑，並且 max_flow 為 0，while 迴圈會不斷增加 max_flow，只要有增廣路徑可以增加流量。
第 35 行：外部 while 迴圈確保 Edmonds-Karp 演算法在有增廣路徑可供增加流量時繼續增加流量。
第 36-37 行：增廣路徑上的初始流量是無限的，並且可能的流量增加將從匯點開始計算。
第 38-40 行：path_flow 的值透過從匯點反向遍歷到源點來找到。沿路徑的殘餘容量的最小值決定了路徑上可以傳送多少流量。
第 42 行：path_flow 會增加 path_flow。
第 44-48 行：遍歷增廣路徑，從匯點反向到源點，前向邊上的殘餘容量會因 path_flow 減少，而反向邊上的殘餘容量會因 path_flow 增加。
第 50-58 行：這部分程式碼僅用於列印，以便我們能夠跟蹤每次找到增廣路徑以及透過該路徑傳送的流量。
定義 Graph 類之後，必須定義頂點和邊以初始化特定的圖，Edmonds-Karp 演算法示例的完整程式碼如下所示
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, c):
self.adj_matrix[u][v] = c
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def bfs(self, s, t, parent):
visited = [False] * self.size
queue = [] # Using list as a queue
queue.append(s)
visited[s] = True
while queue:
u = queue.pop(0) # Pop from the start of the list
for ind, val in enumerate(self.adj_matrix[u]):
if not visited[ind] and val > 0:
queue.append(ind)
visited[ind] = True
parent[ind] = u
return visited[t]
def edmonds_karp(self, source, sink):
parent = [-1] * self.size
max_flow = 0
while self.bfs(source, sink, parent):
path_flow = float("Inf")
s = sink
while(s != source):
path_flow = min(path_flow, self.adj_matrix[parent[s]][s])
s = parent[s]
max_flow += path_flow
v = sink
while(v != source):
u = parent[v]
self.adj_matrix[u][v] -= path_flow
self.adj_matrix[v][u] += path_flow
v = parent[v]
path = []
v = sink
while(v != source):
path.append(v)
v = parent[v]
path.append(source)
path.reverse()
path_names = [self.vertex_data[node] for node in path]
print("Path:", " -> ".join(path_names), ", Flow:", path_flow)
return max_flow
# Example usage:
g = Graph(6)
vertex_names = ['s', 'v1', 'v2', 'v3', 'v4', 't']
for i, name in enumerate(vertex_names):
g.add_vertex_data(i, name)
g.add_edge(0, 1, 3) # s -> v1, cap: 3
g.add_edge(0, 2, 7) # s -> v2, cap: 7
g.add_edge(1, 3, 3) # v1 -> v3, cap: 3
g.add_edge(1, 4, 4) # v1 -> v4, cap: 4
g.add_edge(2, 1, 5) # v2 -> v1, cap: 5
g.add_edge(2, 4, 3) # v2 -> v4, cap: 3
g.add_edge(3, 4, 3) # v3 -> v4, cap: 3
g.add_edge(3, 5, 2) # v3 -> t, cap: 2
g.add_edge(4, 5, 6) # v4 -> t, cap: 6
source = 0; sink = 5
print("The maximum possible flow is %d " % g.edmonds_karp(source, sink))Edmonds-Karp 演算法的時間複雜度
Edmonds-Karp 和 Ford-Fulkerson 的區別在於 Edmonds-Karp 使用廣度優先搜尋（BFS）來尋找增廣路徑，而 Ford-Fulkerson 使用深度優先搜尋（DFS）。
這意味著 Edmonds-Karp 的執行時間比 Ford-Fulkerson 更容易預測，因為 Edmonds-Karp 不受最大流值的影響。
設頂點數為 \(V\)，邊數為 \(E\)，Edmonds-Karp 演算法的時間複雜度為
\[ O(V \cdot E^2) \]
這意味著 Edmonds-Karp 不像 Ford-Fulkerson 那樣依賴於最大流，而是依賴於我們擁有的頂點和邊的數量。
Edmonds-Karp 獲得此時間複雜度的原因是它執行 BFS，其時間複雜度為 \(O(E+V)\)。
但如果我們假設 Edmonds-Karp 的最壞情況，即一個稠密圖，其中邊數 \(E\) 遠大於頂點數 \(V\)，則 BFS 的時間複雜度變為 \(O(E)\)。
BFS 必須為每個增廣路徑執行一次，並且在 Edmonds-Karp 演算法執行期間實際上可以找到接近 \(V \cdot E \) 個增廣路徑。
因此，時間複雜度為 \(O(E)\) 的 BFS 在最壞情況下可以執行接近 \(V \cdot E \) 次，這意味著 Edmonds-Karp 的總時間複雜度為：\( O(V \cdot E \cdot E) = O(V \cdot E^2) \)。
