(Categoria _Grafuri_, autor(i) _Alexandru Mosoi_)
TODO:

* ancore al pasi

* ancore la pasi

* poze si exemplificare
* analiza complexitatii

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

!dinic?Dinic_flow_example_0.png!

!dinic?Dinic_flow_example_1.png!

h2. Descriere

Algoritmul Edmonds-Karp presupune gasirea, cat timp exista, a unui drum de crestere in reteaua reziduala si marirea fluxului total. Evident, la fiecare pas pot exista mai multe drumuri de crestere (care au luO 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? 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 lungime minima de la sursa la destinatie).

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 $v$ (pe scurt, daca muchia $(u, v)$ apartine unui drum de lungime minima de la sursa la destinatie).

In exemplul de mai jos noul graf este construit odata cu parcurgerea in latime. _flow_ reprezinta matricea de adiacenta pentru reteaua reziduala, iar _edges_ memoreaza pentru fiecare nod lista de vecini in graful construit (atentie: muchiile inverse nu apar).