Edmonds–Karp算法

在計算機科學中，Edmonds-Karp算法是用於在O（V E2）時間內計算流網路中的最大流量的Ford-Fulkerson方法的實現。 該算法最初由Yefim Dinitz於1970年出版，並由Jack Edmonds和Richard Karp於1972年獨立出版。Dinic的算法包括將運行時間減少到O（V2 E）的其他技術。

基本介紹

• 中文名：Edmonds–Karp算法
• 外文名：Edmonds–Karp algorithm

算法

該算法與Ford-Fulkerson算法相同，只是定義了找到增廣路徑時的搜尋順序。 找到的路徑必須是具有可用容量的最短路徑。 這可以通過廣度優先搜尋找到，其中我們對每個邊緣套用1的權重。 通過顯示每個增強路徑可以在O（E）時間內找到O（V E2）的運行時間，每次E邊緣中的至少一個變得飽和（具有最大可能流量的邊緣）， 從增強路逕到飽和邊緣到源的距離必須比上次飽和的時間長，並且長度最多為V.該算法的另一個特性是最短增強路徑的長度單調增加。 算法簡介中有一個可訪問的證明。

偽代碼

algorithm EdmondsKarp    input:        graph   (graph[v] should be the list of edges coming out of vertex v.                 Each edge should have a capacity, flow, source and sink as parameters,                 as well as a pointer to the reverse edge.)        s       (Source vertex)        t       (Sink vertex)    output:        flow    (Value of maximum flow)        flow := 0   (Initialize flow to zero)    repeat        (Run a bfs to find the shortest s-t path.         We use 'pred' to store the edge taken to get to each vertex,         so we can recover the path afterwards)        q := queue()        q.push(s)        pred := array(graph.length)        while not empty(q)            cur := q.poll()            for Edge e in graph[cur]                 if pred[e.t] = null and e.t ≠ s and e.cap > e.flow                    pred[e.t] := e                    q.push(e.t)            if not (pred[t] = null)                     (We found an augmenting path.             See how much flow we can send)             df := ∞            for (e := pred[t]; e ≠ null; e := pred[e.s])                df := min(df, e.cap - e.flow)            (And update edges by that amount)            for (e := pred[t]; e ≠ null; e := pred[e.s])                e.flow  := e.flow + df                e.rev.flow := e.rev.flow - df            flow := flow + df        until pred[t] = null  (i.e., until no augmenting path was found)    return flow

例子

給定七個節點的網路，源A，接收器G和容量，如圖1

圖1

在寫在邊上的f / c對中，f是電流，c是容量。 從u到v的剩餘容量是c f（u，v）= c（u，v） - f（u，v），總容量減去已經使用的流量。 如果從u到v的淨流量為負，則有助於剩餘容量。

注意算法（紅色）找到的增強路徑的長度從未減少。 找到的路徑是最短的。 找到的流量等於分隔源和匯的圖中最小切割的容量。 此圖中只有一個最小割，將節點劃分為集合{A，B，C，E}和{D，F，G}，具有容量。

c（A，D）+ c（C，D）+ c（E，G）= 3 + 1 + 1 = 5。