h2. Exemplu
Pentru o mai buna intelegere a articolului vom lucra cu urmatorul exemplu (imagine preluata de pe "Wikipedia"http://en.wikipedia.org"):

(aici vine o imagine).

h2. Descriere
Algoritmul Edmonds-Karp presupune gasirea unui drum de crestere in reteaua reziduala si marirea fluxului total pana cand nu mai exista un drum de crestere. O observatie importanta este ca la fiecare pas in reteua reziduala exista mai multe drumuri de crestere de lungime minima.

Primul pas este sa construim din reteua reziduala un graf orientat aciclic in care sa regasim toate drumurile de lungime minima de la sursa la destinatie. Evident in acest dag toate muchiile vor avea capacitatea cel putin 1. Cum construim acest graf? Pai, destul de simplu. Modificam putin bfs-ul de la Edmonds-Karp ca mai jos. Notam cu _u_ nodul curent, cu _v_ un nod accesibil din u in reteaua reziduala si cu _c_ capactiatea muchiei (u, v) in reteua reziduala. Un nod este vizitat daca a fost scos in coada folosita pentru dfs.
 
* daca v a fost vizitat, nu facem nimic

Primul pas este sa construim din reteua reziduala un graf orientat aciclic in care sa regasim toate drumurile de lungime minima de la sursa la destinatie. Evident in acest dag toate muchiile vor avea capacitatea cel putin 1. Cum construim acest graf? Destul de simplu. Modificam putin bfs-ul de la Edmonds-Karp precum urmeaza. Pentru fiecare nod, calculam distanta (ca numar de muchii) de la sursa pana la el. O muchie (u, v) cu capacitatea c > 0 in reteaua reziduala este adaugata la graful construit doar daca distanta de la sursa la u plus 1 este egala cu distanta de la sursa la nodul u (pe scurt, daca muchia (u, v) apartine unui drum de crestere).

* daca v nu a fost vizitat adaugam muchia (u, v) cu capacitatea c la graful pe care il construim.
 
Aici aveti un exemplu de cod pentru a construi graful. In exemplul de mai jos, din motive care acum nu-mi sunt evidente, ma folosesc distanta pana la nod (initial infinita) pentru a determina daca o muchie trebuie adaugata (sau nu) in graful care se construieste..

Aici aveti un exemplu de cod pentru a construi graful. In codul de mai jos construiesc noul graf odata cu parcurgerea breadth first. _flow_ reprezinta matricea de adiacenta pentru reteaua reziduala, iar _edges_ memoreaza pentru fiecare nod lista de vecini in graful construit.

== code(c) |
while (!que.empty()) {

	}
}
==

 
Scriind acest articol, mi-am dat seama ca se putea un pic mai simplu, fara sa tin cont de distanta.