Drumul de ameliorare il vom determina folosind un BFS (cautare in latime) si in loc sa marim fluxul cu o singura unitate, vom mari fluxul cu valoarea minima dintre capacitatile de pe drumul de amelioarare. Se observa intuitiv ca dupa saturarea unui drum de ameliorare se satureaza cel putin o muchie. Dupa O(M) saturari de drumuri se observa ca cel mai scurt drum de la sursa la destinatie trebuie sa creasca. Asadar dupa O(N*M) astfel de operatii destinatia nu va mai fi accesibila din sursa si prin urmare avem fluxul maxim. Cum fiecare operatie (din cele O(N*M) ) au complexitate O(M+N) (BFS) rezulta complexitatea finala O(N* M^2).

==code(c) |
#include <cstdio>
#define N 128
#define oo 0x3f3f3f3f //infinit
int cap[N][N], flux[N][N];
int t[N];//t= vector de tati
int n, m;
 
int bfs(int source, int sink)
{
	int Q[N+1], p=0,q=0;
	bool use[N];
	memset(use, 0, sizeof(use));
	memset(t, 0, sizeof(t));
	Q[0]=source;
	use[source]=1;
 
	while(p<=q)
	{
		int u=Q[p++];//scoatem primul element din coada
 
		for(int i=1;i<=n;++i) // pt fiecare nod ( adiacent )
			if(!use[i]) // nu am folosit nodul
				if(cap[u][i] - flux[u][i] > 0) // mai putem pompa?
				{
					Q[++q]=i; // inseram nodul i in coada
					t[i]=u;
					use[i]=1;
				}
	}
 
	if(t[sink]) return 1;
	return 0;
}
 
int edmond-karp(int source, int sink)
{
	int flow=0; //fluxul
	int i, min;
 
	while(bfs(source, sink)) // cat timp mai exista un drum de ameliorare
	{
		min=oo;
		for(i=sink; i; i=t[i])
			if(cap[i] > min) min=cap[i]; //calculam minimul dintre capacitatile de pe drum
 
		for(i=sink ; i; i=t[i])
			f[t[i]][i]+=min, //adaugam minimul la fluxul de pe arcele de pe drum
			f[i][t[i]]-=min; //scadem minimul de pe arcele inverse
 
		flow+=min; // adaugam minimul la flux
	}
 
}
 
==