mareste fluxul f de-a lungul drumului p
      returneaza f
==

 
Ce este un drum de ameliorare? Un drum de ameliorare este un drum de la sursa la destinatie care are proprietatea ca fiecare muchie are cap[i]-flux[i] > 0,
sau mai bine zis, "se mai poate pompa lichid prin conductele ce compun drumul".
 
Conform acestei metode se poate implementa un algoritm cu o complexitate ce depinde de capacitati (marim fluxul cu o unitate la fiecare pas).
 
Edmonds si Karp au dat urmatorul algoritm ce are complexitate O(N *M^2):
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).