(Categoria _Grafuri_, autor(i) _Alexandru Mosoi_)

TODO:
* ancore al pasi
* poze si exemplificare
 

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.

	return bag;
}

==

==
 
Functia do_df() pompeaza fluxul maxim in graful construit la **pasul 1**. Datorita formei particulare a grafului si ca forma sa nu se schimba dupa fiecare drum de crestere algoritmul nu are deficienta intalnita la algoritmul Ford-Fulkerson.
 
h3. Pasul 3
 
Cat timp mai exista drum de crestere (sau fluxul introdus la pasul anterior este strict pozitiv) reiau algoritmul de la **Pasul 1**.