~ Algoritma Edmonds-Karp ~

Dalam ilmu komputer , algoritma Edmonds-Karp adalah implementasi metode Ford-Fulkerson untuk menghitung aliran maksimum dalam jaringan arus pada waktu O ( V E ² ). Algoritma ini pertama kali diterbitkan oleh Yefim Dinitz pada tahun 1970  dan diterbitkan secara independen oleh Jack Edmonds dan Richard Karp pada tahun 1972. ^[3] Algoritma Dinic mencakup teknik tambahan yang mengurangi waktu berjalan ke O ( V ² E ).

Algoritma

Algoritma ini identik dengan algoritma Ford-Fulkerson , kecuali bahwa urutan pencarian saat menemukan jalan augmenting didefinisikan. Jalur yang ditemukan pastilah jalan terpendek yang memiliki kapasitas yang tersedia. Ini bisa ditemukan dengan pencarian yang luas , karena kita membiarkan tepi memiliki panjang satuan. Waktu berjalan O ( V E ² ) ditemukan dengan menunjukkan bahwa setiap jalur augmenting dapat ditemukan pada waktu O ( E ), bahwa setiap kali setidaknya satu dari ujung E menjadi jenuh (tepi yang memiliki arus maksimum) , bahwa jarak dari tepi jenuh ke sumber sepanjang jalan augmenting harus lebih lama dari waktu terakhir jenuh, dan panjangnya paling banyak V. Sifat lain dari algoritma ini adalah bahwa panjang jalur augmenting terpendek meningkat secara monoton. Ada bukti yang mudah diakses dalam Introduction to Algorithms .


Ini adalah contoh Pseudo Code dari Algoritma Edmonds-Karp

Pseudocode

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

Given a network of seven nodes, source A, sink G, and capacities as shown below:

In the pairs ${\displaystyle f/c}$ written on the edges, ${\displaystyle f}$ is the current flow, and ${\displaystyle c}$ is the capacity. The residual capacity from ${\displaystyle u}$ to ${\displaystyle v}$ is ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$, the total capacity, minus the flow that is already used. If the net flow from ${\displaystyle u}$ to ${\displaystyle v}$ is negative, it contributes to the residual capacity.

Capacity	Path	Resulting network
${\displaystyle {\begin{aligned}&\min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))\\=&\min(3-0,2-0,1-0)=\\=&\min(3,2,1)=1\end{aligned}}}$	${\displaystyle A,D,E,G}$
${\displaystyle {\begin{aligned}&\min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-1,6-0,9-0)\\=&\min(2,6,9)=2\end{aligned}}}$	${\displaystyle A,D,F,G}$
${\displaystyle {\begin{aligned}&\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-0,4-0,1-0,6-2,9-2)\\=&\min(3,4,1,4,7)=1\end{aligned}}}$	${\displaystyle A,B,C,D,F,G}$
${\displaystyle {\begin{aligned}&\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-1,4-1,2-0,0-(-1),6-3,9-3)\\=&\min(2,3,2,1,3,6)=1\end{aligned}}}$	${\displaystyle A,B,C,E,D,F,G}$

Notice how the length of the augmenting path found by the algorithm (in red) never decreases. The paths found are the shortest possible. The flow found is equal to the capacity across the minimum cut in the graph separating the source and the sink. There is only one minimal cut in this graph, partitioning the nodes into the sets ${\displaystyle \{A,B,C,E\}}$ and ${\displaystyle \{D,F,G\}}$, with the capacity

${\displaystyle c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\ }$