Algoritmul Ford-Fulkerson

Algoritmul Ford-Fulkerson

Algoritmul Ford-Fulkerson Aceasta este o metodă iterativă de găsire a fluxului maxim într-un graf care pleacă de la ideea: cât timp mai există un drum de ameliorare (o cale de la sursă la destinație) pot pompa pe această cale un flux suplimentar egal cu capacitatea reziduală a căii.

Acest algoritm reprezintă mai mult un șablon de rezolvare pentru că nu detaliază modul în care se alege drumul de ameliorare din rețeaua reziduală.

algoritm Ford_Fulkerson(G)C
    // G    rețeaua de transport
    // aij reprezintă capacitatea unui arc de la nodul i la nodul j 
    creează matricea a
    flux_maxim = 0
    cât_timp există drumuri de creștere execută
       determină un drum de creștere D
       min = ∞
       pentru fiecare muchie (i, j) din D execută
          dacă aij < min atunci
             min = aij
          sfârșit dacă
          flux_maxim = flux_maxim + min
       sfârșit pentru
       pentru fiecare muchie (i, j) din D execută
          aij <— aij - min
          aji <— aji + min
       sfârșit pentru
    sfârșit cât timp
sfârșit algoritm

Complexitatea va fi O(E * f max) pentru că în ciclul while putem găsi, în cel mai rău caz, doar cai care duc la creșterea fluxului cu doar o unitate la fiecare pas.

Ne punem acum problema dacă acest algoritm este corect, dacă la final vom avea cu adevărat fluxul maxim posibil prin graf. Corectitudinea algoritmului derivă imediat din teorema Flux maxim - tăietura minimă.

Numim o tăietură a unui graf o partiție (S,T) a nodurilor sale cu proprietatea s∈S si t∈T.

Teorema flux maxim – tăietura minimă:

Pentru o rețea de flux G(V,E) următoarele afirmații sunt echivalente:

1. f este fluxul maxim în G

2. Rețeaua reziduală Gf nu conține drumuri de ameliorare

3. Există o tăietură (S,T) a lui G astfel încât fluxul net prin tăietură este egal cu capacitatea acelei tăieturi.

Obs: Prin orice tăietură fluxul este egal cu cel maxim pentru că nu există o altă cale pe care ar putea ajunge flux de la sursă la destinație și care să nu treacă prin tăietură (ar încălca tocmai definiția ei); sau, altfel spus, valoarea unui flux într-o rețea este dată de fluxul oricărei tăieturi. Astfel, fluxul total va fi mărginit de cea mai mică capacitate a unei tăieturi. Dacă este îndeplinit punctul 3. al teoremei atunci știm că acea tăietură nu poate fi decât una de capacitate minimă. Ultima incercare de a gasi o cale de la sursa la drena va rezulta in gasirea doar a elementelor marginite de o astfel de taietura.

Exemplu:

Rețeaua inițială:


Rețeaua reziduală:


Observăm că deși muchia (d,c) are capacitate 0 în rețeaua originală (ea nu ar putea transporta flux) în rețeaua reziduală avem c(d,c)=1 ceea ce îi permite să facă parte din drumul de ameliorare p1 = ( s,a,b,d,c,t) de capacitate cf (p1)=1, astfel că adăugarea acestui flux suplimentar pe muchia (d,c) nu va duce la încălcarea restricției de capacitate; sau am fi putut alege drumul p2=(s,a,c,t) cu cf(p2)=1 sau p3=(s,a,b,d,t) cu cf(p3)=1.
Performanța algoritmului ține de modul în care va fi ales drumul de ameliorare, se poate întâmpla ca pentru |fmax| de valoarea mare o alegere nepotrivită să ducă la timpi de execuție foarte mari.