Flux maxim intr-o retea de transport, algoritmul lui Dinic

(Categoria Grafuri, autor(i) Alexandru Mosoi)

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.