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