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.
 
h2. Exemplu
 
Pentru o mai buna intelegere a articolului vom lucra cu urmatorul exemplu (imagine preluata de pe "Wikipedia"http://en.wikipedia.org"):
 
 
 
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
 

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.