Algoritmul Ford Fulkerson

Algoritmul Ford-Fulkerson este unul din algoritmii cei mai simpli care rezolvă problema “Debitului maxim”. Constă în 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. Materiale media legate de Algoritmul Ford Fulkerson la Wikimedia Commons