h2. Introducere

Acest articol presupune o familiarizare anterioara cu grafuri si retele de transport. Pentru a elimina neclaritati vom da urmatoarea definitie: _O **retea de transport** este un graf orientat in care avem un nod **sursa**, un nod **destinatie**, iar fiecarei muchii ii este asociata o capacitate superioara_. Problema este clasica: cat flux putem baga de la sursa la destinatie fara a depasi capacitatea fiecarei muchii. Algoritmul pe care probabil deja il cunoasteti poarta numele "Edmonds-Karp":http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm si are complexitatea O(N*M*M). Algoritmul **Dinic**, prezentat in acest articol, are complexitatea O(N*N*M). Am folosit notatiile obisnuite: $N$ - numarul de noduri, $M$ - numarul de muchii.

Acest articol presupune o familiarizare anterioara cu grafuri si retele de transport. Pentru a elimina neclaritati vom da urmatoarea definitie: _O **retea de transport** este un graf orientat in care avem un nod **sursa**, un nod **destinatie**, iar fiecarei muchii ii este asociata o capacitate superioara_. Problema este clasica: cat flux putem baga de la sursa la destinatie fara a depasi capacitatea fiecarei muchii. Algoritmul pe care probabil deja il cunoasteti poarta numele "Edmonds-Karp":http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm si are complexitatea O(N*M*M). Algoritmul **Dinic**, prezentat in acest articol, are complexitatea O(N*N*M). Am folosit notatiile obisnuite: N - numarul de noduri, M - numarul de muchii.

h2. Exemplu

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? 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 u (pe scurt, daca muchia (u, v) apartine unui drum de crestere).

In exmplul codul 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.

Aici aveti un exemplu de cod pentru a construi graful. In codul 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.

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