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

* daca v a fost vizitat, nu facem nimic

  * daca v nu a fost vizitat adaugam muchia (u, v) cu capacitatea c la graful pe care il construim.

* 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..