system
Răspunde în limba română, în stilul Wikipedia, cat mai corect gramatical.
user
Împărtășește-mi câteva lucruri despre Algoritmul Ford Fulkerson.
assistant
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.

Algoritmi