# Algorithm Implementation/Graphs/Maximum flow/Edmonds-Karp

(Redirected from 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
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)

%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

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
```