Algorithm Implementation/Graphs/Maximum flow/Edmonds-Karp

Java

import java.util.*;
 
/**
 * Finds the maximum flow in a flow network.
 * @param E neighbour lists
 * @param C capacity matrix (must be n by n)
 * @param s source
 * @param t sink
 * @return maximum flow
 */
public class EdmondsKarp {
    public static int edmondsKarp(int[][] E, int[][] C, int s, int t) {
        int n = C.length;
        // Residual capacity from u to v is C[u][v] - F[u][v]
        int[][] F = new int[n][n];
        while (true) {
            int[] P = new int[n]; // Parent table
            Arrays.fill(P, -1);
            P[s] = s;
            int[] M = new int[n]; // Capacity of path to node
            M[s] = Integer.MAX_VALUE;
            // BFS queue
            Queue<Integer> Q = new LinkedList<Integer>();
            Q.offer(s);
            LOOP:
            while (!Q.isEmpty()) {
                int u = Q.poll();
                for (int v : E[u]) {
                    // There is available capacity,
                    // and v is not seen before in search
                    if (C[u][v] - F[u][v] > 0 && P[v] == -1) {
                        P[v] = u;
                        M[v] = Math.min(M[u], C[u][v] - F[u][v]);
                        if (v != t)
                            Q.offer(v);
                        else {
                            // Backtrack search, and write flow
                            while (P[v] != v) {
                                u = P[v];
                                F[u][v] += M[t];
                                F[v][u] -= M[t];
                                v = u;
                            }
                            break LOOP;
                        }
                    }
                }
            }
            if (P[t] == -1) { // We did not find a path to t
                int sum = 0;
                for (int x : F[s])
                    sum += x;
                return sum;
            }
        }
    }
}

MATLAB

This code is the direct transcription in MATLAB language of the pseudocode shown in the Wikipedia article of the Edmonds-Karp algorithm.

function [f,F]=EdmondsKarp(C,E,s,t)
 
%Initial flow is 0
f=0;
 
imax=size(C,1);
F=zeros(imax);
 
while(1)
    [m,P]=BreadthFirstSearch(C,E,s,t,F);
 
    %The end is reached when the capacity of the returned path is 0
    if(m==0)
        break;
    end
 
    %The total flow is increased by m
    f=f+m;
 
    %The flow for every edge on the path is increased by m
    v=t;
    while(v~=s)
        u=P(v);
        F(u,v)=F(u,v)+m;
        F(v,u)=F(v,u)-m;
        v=u;
    end
end
 
end
 
 
function [M,P]=BreadthFirstSearch(C,E,s,t,F)
 
n=size(C,1);
P=zeros(n,1);
M=zeros(n);
M(s)=Inf;
 
for u=1:n
    P(u)=-1;
end
P(s)=-2;
 
%Q is used as a queue
Q=[];
Q=vertcat(Q,s);
 
while(isempty(Q)==0)
    u=Q(1);
    Q(1)='';
 
    neighbors=E{u};
    for i=1:length(neighbors)
        v=neighbors(i);
        if(C(u,v)-F(u,v)>0 && P(v)==-1)
            P(v)=u;
            M(v)=min(M(u),C(u,v)-F(u,v));
            if(v~=t)
                Q(length(Q)+1)=v;
            else
                M=M(t);
                return;
            end
        end
    end
end
 
M=0;
 
end