Algoritmul Ford Fulkerson

De la Wikipedia, enciclopedia liberă

Acest articol trebuie pus în formatul standard Ştergeţi eticheta la încheierea standardizării. Articolul a fost etichetat în luna iulie 2007.

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.

Datorită faptului că un drum de creştere conţine arce care au costuri pozitive, valoarea sa va fi întotdeauna un număr pozitiv. Ca urmare, pentru fiecare drum de creştere determinat, valoarea fluxului va creşte cu cel puţin o unitate. Datorită faptului că avem capacităţi finite, fluxul maxim este un număr finit. Din aceste motive suntem siguri că, mai devreme sau mai târziu, algoritmul se va încheia.

Determinarea unui drum de creştere se poate realiza prin orice metodă dar, din motive de eficienţă, trebuie utilizată una al cărei ordin de complexitate este Θ(M + N). Din nefericire, algoritmul ne asigură doar faptul că la fiecare pas valoarea fluxului va creşte cu cel puţin o unitate. Aşadar, dacă fluxul maxim este F, există posibilitatea de a efectua F paşi. Ca urmare, ordinul de complexitate al algoritmului Ford-Falkerson este Θ(F • (M + N)). Se observă că, în cazul în care valoarea fluxului este foarte mare, acest ordin de complexitate este inacceptabil.

Vom prezenta în continuare versiunea în pseudocod a algoritmului.

algoritm Ford_Fulkerson(G)
    // 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

Practic se va încerca la fiecare pas determinarea unui drum de creştere şi algoritmul se va opri în momentul în care nu mai poate fi găsit nici un astfel de drum.

De obicei, este necesară şi determinarea valorilor funcţiei f (fluxul pe un anumit arc). Pentru aceasta este suficient să se afişeze costurile arcelor speciale.