# Edmonds Karp Algorithm

The Edmonds-Karp algorithm has an execution time of O(VE²), it is faster than the Ford-Fulkerson algorithm for dense graphs, ie a graph containing a large number of edge (or arcs) according to the number of vertices.

The algorithm is identical to the Ford-Fulkerson algorithm, except for the search order used to determine an increasing path. The path found must be the shortest path that has a positive ability. Such a path can be found by a path in width, assuming that the arcs all have a unit length. Note that the length of the increasing path increases with each iteration.
```From wikipédia
```
```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```
```algorithm BreadthFirstSearch
input:
C, E, s, t, F
output:
M[t]
P
P := array(1..n)
for u in 1..n
P[u] := -1
P[s] := -2
M := array(1..n)
M[s] := ∞
Q := queue()
Q.push(s)
while Q.size() > 0
u := Q.pop()
for v in E[u]
if C[u,v] - F[u,v] > 0 and P[v] = -1
P[v] := u
M[v] := min(M[u], C[u,v] - F[u,v])
if v ≠ t
Q.push(v)
else
return M[t], P
return 0, P```

Publicités