Problema Determinării unui Flux Maxim

Având dată o reţea de transport să se determine un flux astfel încât fluxul la ieşirea reţelei să fie maxim.

Algoritmi pentru rezolvarea problemelor de flux într-o reţea de transport au fost dezvoltaţi de:

 Ford, Fulkerson (1956),

 Edmonds, Karp (1969),

 Dinic (1970), Karzanov (1973),

 Cherkassky (1976),

 Malhotra şi alţii (1978), Galil (1978),

 Galil şi Naamad (1979),

 Sleator şi Tarjan (1980),

 Goldberg şi Tarjan (1985).

Se da o retea de transport sub forma unui graf orientat cu N noduri si M arce. Fiecare arc are asociata o capacitate si un cost pentru fiecare unitate de flux ce trece pe arcul respectiv. Notam cu S si D sursa si respectiv destinatia din reteaua de transport considerata. Sa se determine costul minim pentru a se transmite o cantitate maxima de flux de la sursa la destinatie.

Indicatii de rezolvare

Aceasta problema se rezolva in mod asemanator cu problema determinarii fluxului maxim cu cateva modificari. Este din nou necesara constuirea grafului rezidual, care contine toate arcele din graful initial si, in plus, toate arcele de intoarcere. Astfel, pentru fiecare arc x->y de cost z din graful initial se adauga in graful rezidual arcul y->x cu capacitatea 0 si costul -z. Algoritmul ruleaza atat timp cat se mai poate introduce flux in retea. La fiecare pas, este necesara gasirea unui drum de ameliorare de cost minim de la sursa la destinatie. Apoi, fluxul va fi incrementat pe acest drum cu valoarea maxima posibila (minimul diferentelor dintre capacitate si flux pentru fiecare arc de pe drum). Pentru a gasi drumul de ameliorare optim din punct de vedere al costului putem folosi un algoritm de drum minim care sa permita existenta costurilor negative pe arce (costurile arcelor de intoarcere), precum Bellman-Ford Algoritmul Bellman-Ford are complexitate O(N*M), ceea ce conduce la o complexitate teoretica O(N2*M2), insa in practica se comporta mai bine. Algoritmul Bellman-Ford poate fi rafinat folosind o coada pentru a mentine nodurile ce mai pot contribui la imbunatatirea costurilor. Desi complexitatea ramane aceeasi, in practica timpul de rulare scade simtitor.

Pentru a imbunatati algoritmul de mai sus, atunci cand cautam drumul de ameliorare de cost minim putem folosi si algoritmul lui Dijkstra, dar inainte graful trebuie modificat astfel incat sa nu mai exista arce cu cost negativ.Algoritmul lui Dijkstra are complexitate O(M*logN), deci complexitatea totala devine O(N*M2*logN), dar este iarasi supraestimata.

Aplicatii

Algoritmul de flux maxim si cost minim poate fi aplicat si pentru grafuri neorientate cu modificari minime. In plus, poate fi aplicat si pentru determinarea cuplajului de cost minim intr-un graf bipartit. De asemenea, putem determina si cuplajul de cost maxim intr-un graf biparit, folosind acelasi algoritm dupa ce costul fiecarei muchii a fost inlocuit cu diferenta dintre valoarea maxima a unei muchii si valoarea curenta. In acest caz, rezultatul va fi egal cu diferenta dintre produsul fluxului si valoarea maxima a unei muchii si costul fluxului obtinut pe graful modificat.

Algoritmul Ford-Fulkerson

Algoritmul Ford-Fulkerson constă in identificarea succesivă a unor drumuri de creştere până în momentul în care nu mai există nici un astfel de drum.

După identificarea unui drum de creştere se determină valoarea acestuia, iar aceasta se scade din costurile fiecărui arc (i, j) de pe drumul respectiv şi se adună la costurile arcelor corespunzătoare de forma (j,i). De asemenea, valoarea respectivă se adună la fluxul maxim determinat până în momentul respectiv.