Algoritm Pentru Determinarea Fluxului Minim în Retele

Cuvânt înainte

Am ales această temă deoarece mie mi se pare foarte provocatoare,adică cuprinde algoritmi de aflare a fluxului minim într-o rețea, foarte compleți din punct de vedere a abordării problemei de flux minim. Deși, algoritmii care determina fluxuri sunt folosiți practi, totuși eu mă gandesc că acești algoritmi ce determină, fie fluxuri maxime fie fluxuri minime ,ar putea fi folosiți in administrarea rețelei de apa a oricărui mare oraș. De exemplu într-un oraș mare precum Brașovul ar fi foarte util ca rteaua de apă a orașului să folosească un astfel de algoritm care să fie adaptat astfel încât la o anumită defecțiune de-a lungul rețelei programul care monotorizează rețeaua sa emită un avertisment.

În lucrare, în primul capitol enumăr majoritatea definițiilor care au legătură cu titlul lucrării.

În capitolul al doilea prezint anumiți algoritmi care determină fluxuri minime dar care sunt adaptați pentru acest lucru, ei fiind inițial obținuți pentru a determina fluxuri maxime. Dupa o scurta prezentare a modului de funcționare a ficărui algoritm pe care l-am prezentat în lucrare am dat un cod sursă adaptat pentru C++, iar apoi câte un exemplu care explică mai bine funcționarea fiecărui algoritm.

Pentru realizarea acestei lucrări m-am inspirat din carțile și manualele de informatică pe sunt enumerate la finalul lucrării.

Cap 1. Noțiuni introductive(Definiții)

Vocabular de bază pentru fluxuri minime

Definiția 1.1.1. Se numește graf orientat un triplet G = (N ,A ,g) format dintr-o mulțime N de elemente numite noduri sau vârfuri, dintr-o familie A de elemente numite arce și dintr-o aplicație g : A → Nx N numită funcție de incidență, prin care fiecărui element a A i se asociază o pereche ordonată (x,y) N x N cu x ≠ y; dacă eliminăm condiția x ≠ y atunci arcul de forma (x,x) se numește buclă; iar G se numește graf general orientat.

În continuare vom presupune că graful orientat G este finit, adică mulțimea nodurilor N = {…,x,…} este finită și familia arcelor A = (…,a,…) este un șir finit. Cardinalul mulțimii N notat |N| = n, se numește ordinul grafului orientat G.

Un graf orientat G = (N ,A ,g) se reprezintă grafic în modul următor:

i. fiecare nod x N se reprezintă printr-un punct sau cerculeț în plan;

ii. fiecare arc a A, a = (x,y) se reprezintă printr-o linie care unește cele două noduri și pe care se afla o sageată cu sensul de la x la y.

Observația 1.1.1. Reprezentarea grafică a unui graf orientat G = (N ,A ,g) nu este unică. În primul rând nodurile se pot plasa în plan la intâmplare. În al doilea rând nu este obligatoriu ca arcele să fie segmente de dreaptă.

Definiția 1.1.2. Două grafuri orientate G1= (N1 ,A1 ,g1) și G2 = (N2 ,A2 ,g2) se numesc izomorfe, dacă există o bijecție ø : N1 → N2 cu proprietatea că aplicația ψ: A1→ A2 , definită prin ψ(x1,y1) = (ø(x1), ø(y1)), (x1,y1) A1 , (ø(x1), ø(y1)) = (x2,y2) A2, este o bijecție.

Definiția 1.1.3. Dacă oricare pereche ordonată (x,y) N x N este imaginea a cel mult q, q > 1, elemente din A, atunci G = (N, A, g) se numește multigraf orientat.

Definiția 1.1.4. Se numește graf orientat un triplet G = (N, A, g) format dintr-o mulțime N de elemente numite noduri sau vârfuri, dintr-o familie A de elemente numite muchii și dintr-o aplicație g : A → P(2)(N) numită funcție de incidență, prin care fiecărui element a A i se asociază o pereche{x,y} P(2)(N); dacă considerăm g : A → P(2)(N), unde P(2)(N) = P(2)(N) P(1)(N), atunci aplicația g asociază fiecărui element a A, fie o pereche de noduri {x,y} P(2)(N) care se notează [x,y] sau [y,x], fie un nod {x} P(1)(N) care se notează [x,x] și se numește buclă, iar G se numește graf general neorientat.

Definiția 1.1.5. Fie un arc a = (x,y) A. Nodul x se numește predecesor al nodului y și nodul y se numește successor al nodului x. Mulțimea succesorilor nodului x este mulțimea V+(x) = {y | (x,y) A} și mulțimea predecesorilor nodului x este mulțimea V-(x) = (y | (y,x) A}. Mulțimea V(x) = = V+(x) U V-(x) se numește vecinătatea nodului x. Dacă V(x) = ø, atunci x se numește nod izolat.

Definiția 1.1.6 Fie arcul a = (x,y ) A. Se spune că arcul a este incident către exterior la nodul x și incident către interior la y. Mulțimea arcelor incidente către exterior la nodul x este E(x) = { a | a= (x,y ) A}, mulțimea arcelor incidente către interior la nodul x este E(t) ={ a| a = (x,y ) A} și nulțimea arcelor incidente la nodul x este E(x) = E(x) E(x). NUmărul ρ(x) = | E(x)| se numește semigradul exterior al nodului x , numărul ρ(x) = |E(t)| se numește semigrdul interior al nodului x și numărul ρ(x) = ρ(x) + ρ(x).

Fie G = (N,A) un digraf cu mulțimea nodurilor N = {1, . . . ,n} și mulțimea arcelor A = {1, . . . ,m}. Matricea de adiacență asociată digrafului G este matricea:

M = (m )

unde

m= 1 dacă (i,j) A

dacă (i,j) A

Evident au loc relațiile:

ρ(i) = m, j N ρ(j) = m, j N.

Matricea de incidență asociată digrafului G este matricea M = (m’) unde

1 dacă j E(x)

m’ = -1 dacă j E(t)

0 dacă j E(i)

În acest caz au loc relațiile:

ρ(i) = m’ , j N ρ(i) = m’ , j N.

Clase de grafuri

Definiția 1.2.1 Se spune că digraful G =(N,A) este simetric dacă oricare ar fi arcul (x,y ) A implică (y,x ) A.

Definiția 1.2.2 Se spune că digraful G =(N,A) este antisimetric dacă oricare ar fi arcul (x,y ) A implică (y,x ) A.

Definiția 1.2.3 Se spune că digraful G =(N,A) este pseudometric dacă ρ(x) = ρ(x) pentru fiecare nod x N.

Definiția 1.2.4 Se spune că digraful G =(N,A) este complet dacă oricare ar fi arcul (x,y) A (y,x ) A (de exemplu digraful din figura urmatoare este complet)

Fig 1.1

Un digraf neorientat G = (N,A) cu n noduri care este complet se notează cu K și are n(n – 1)/2 muchii.

Definiția 1.2.5 Se spune că digraful G =(N,A) este o ciclă dacă este simetric și complet. Denumirea de ciclă se justifică prin faptul că un digraf simetric și complet poate reprezenta o circulație sociologică, politică etc.

Structuri de reprezentare și utilizare în reprezentarea grafurilor

Fie un digraph G = (N,A) cu N = {1, . . . ,n} și A = {1, . . . ,m}. Se consideră funcția valoare b : A și functia capacitate c : A . Funcția valoare b reprezintă fie funcția lungime, fie funcția cost etc.

Definiția 1.3.1 Un digrf G = (N,A) pe care s-a/s-au definit funcția b sau/și funcția c se numește rețea orientată și se notează G = (N,A,b) , fie G = (N,A,c) respective G = (N,A,b,c) .

Reprezentarea rețelei se poate face folosind una din matricile (adiacență/incidență) prezentate în paragraful anterior.

Memorarea funcțiilor definite mai sus, se face folosind matrici,astfel:

B = (b)

unde

b= b(i,j) dacă (i,j) A

0 dacă (i,j) A

Este reprezentarea matricei valoare, iar următoarea reprezentare este cea a matricei capacitate:

C = (c)

unde

c= b(i,j) dacă (i,j) A

dacă (i,j) A.

1.4 Noțiuni de complexitate a algoritmilor

Definiția 1.4.1 Prin problemă se înțelege o funcție total definită P : I F, unde I este mulțimea informațiilor inițiale (datele de intrare ale problemei) și F este mulțimea informațiiloe finale (datele de ieșire ale problemei).

Definiția 1.4.2 Se numește instanță a problemei P , precizarea problemei P(i) pentru o valoare specificată i I.

Un algoritm este o procedură care rezolvă pas cu pas o instanță p, p P.

Definiția 1.4.3 Se spune că algoritmul α rezolvă problema P dacă algoritmul determină soluția oricarei instanțe p P.

Definiția 1.4.4 Se numește dimensiunea problemei P un număr natural notat d(p), p P, care reprezintă lungimea unei codificări binare a informației inițiale.

Definiția 1.4.5 Se numește complexitatea timp(sau simplu complexitate) a algoritmului α comportarea asimptotică a lui T(k), unde T(k) = M{T(p) | p P, d(p) = k} (reprezintă timpul de execuție necesar algoritmului α pentru rezolvarea instanței p, p P). Se spune că o problemă algoritmică P are complexitatea O(f(k)) dacă există un algoritm α care rezolvă problema P și algoritmul α are complexitatea T(k) = O(f(k)).

1.5 Parcurgeri de grafuri

Problema parcurgerii unui digraph G =(N,A) , N = {1, . . . ,n} și A = {1, . . . ,m} are următoarea formulare: să se genereze mulțimea W N a nodurilor y pentru care există drum de la un ndo sursa dat s la nodul y în digraful G. Dacăexistadrum , în digrful G, de la nodul sursă s la nodul y atunci se spune că nodul y este accesibil din nodul s.

Fiecare iterație a execuțeie oricărui algoritm de parcurgere stabilește pentru fiecare nod apartenența la una din următorele trei stări:

• nevizitat

• vizitat și neanalizat, adică un nod vizitat ai cărui succesori au fost parțial vizitați

• vizitat și analizat, adică un nod vizitat ai cărui succesori au fost în totalitate vizitați

Dacă nodul x este vizitat și neanalizat, există arc (x,y) și nodul y este nevizitat, atunci se poate vizita nodul y. În acest caz saspuns că arcul (x,y) este arc admisibil și dacă nodul y este vizitat explorând arcul (x,y) se spune că nodul x este predecesorul parcurgere al lui y, iar y este succesorul parcurgere al lui x.

Unul din algoritmii de parcurgere a uni digraph este algoritmul generic care utilizează urmatoarele notații:

U mulțimea nodurilor nevizitate;

V mulțimea nodurilor vizitate și neanalizate

W mulțimea nodurilor vizitate si analizate

p vectorul predecesor, care are n elemente

iar forma algoritmului este urmatoarea:

includeri de biblioteci și declarări;

void pg();

{ U= N – {s}; V = {s}; W = ø;

FOR toți y N

d(y) = 0;

k = 1; o(s) = 1;

FOR toți y N

o(s) = ;

WHILE V ø

{ Se selectează un nod x din V;

IF există arc (x,y ) A și y U

{ U = U – {y}; V = V {y};

d(y) = x; k = k+ 1; o(y) = k; }

ELSE V = V- {x]; W = W {x};

}

}

Cap.2 Algoritmi pentru determinarea fluxului minim

în rețele

Noțiuni introductive

Problema fluxuilui minim de la nodul sursă s la nodul stoc t în rețeaua G=(N,A,l,c,s,t) constă în a determina funcția f :A→ care îndeplineste constrângerile:

minimizează v (2.1a)

v, dacă x = s

─ = v, dacă x ≠ s,t (2.1b)

-v, dacă x = t

l(x ,y)≤f(x,y)≤c(x,y), (x,y) A. (2.1c)

Pentru problema fluxului minim, un preflux este o functie f : A → care îndeplinește condițiile :

─ ≤ 0 x N \ {s,t} (2.2a)

l( x,y) ≤ f(x,y) ≤ c(x,y) (2.2b)

Fie f un preflux. Deficitul fiecãrui nod x N este definit astfel:

e(x) = ─ (2.3)

Spunem cã un nod x este echilibrat dacă e(x) = 0. n preflux f care îndeplinește condiția

e(x) = 0, x N \ {s,t}

este un flux. Deci v, dacă x ≠ s,t (2.1b)

-v, dacă x = t

l(x ,y)≤f(x,y)≤c(x,y), (x,y) A. (2.1c)

Pentru problema fluxului minim, un preflux este o functie f : A → care îndeplinește condițiile :

─ ≤ 0 x N \ {s,t} (2.2a)

l( x,y) ≤ f(x,y) ≤ c(x,y) (2.2b)

Fie f un preflux. Deficitul fiecãrui nod x N este definit astfel:

e(x) = ─ (2.3)

Spunem cã un nod x este echilibrat dacă e(x) = 0. n preflux f care îndeplinește condiția

e(x) = 0, x N \ {s,t}

este un flux. Deci, un flux este un caz particular de preflux.

Pentru problema fluxului minim, capacitatea reziduală a arcului (x,y) corespunzătoare prefluxului f se definește astfel:

r(x,y) = c(xy,x) ─ f(y,x) + f(x,y) ─ l(x,y).

Ipoteză. Dacă arcul (x,y) A, atunci arcul (y,x) A.

Această ipoteză este restrictivă deoarece dacă (x,y) A și (y,x) A, atunci seconsideră că arcul (y,x) є A cu c(y,x) = 0, atunci dacă arcul (x,y) apartine rețele,atunci și arcul (y,x) aparține rețelei. Cpacitatea reziduală r(x,y) a arcului (x,y) reprezintă cantitatea maximă cu care se poate micșora fluxul de la nodul x la nodul y. Rețeaua reziduală Ĝ(f)=(Ń,Á) cores-punzătoare prefuluxului f este formată doar din arcele cu capacitãț I reziduale positive, adică din arcele (x,y) cu r(x,y) > 0.În figura 1.1(b) este reprezentată rețeaua reziduală Ĝ(f) corespunzătoare prefluxului f din rețeaua din figura 2.1(a).

Fig.2.1(a)

Fig. 2.1(b)

Pentru problema fluxului minim, definim capacitatea ĉ[X,X’] a unei tăieturi s ─ t [X,X’] ca fiind diferența dintre suma marginilor laterale ale arcelor directe și suma capacităților inverse, adică

ĉ[X,X’] = l(X,X’) ─ c(X’,X).

O tăietură s ─ t a cărei capacitate este maximă se numește tăietură maximă.

Dacă în rețeaua G = (N,A,l,c,s,t) f este un flux și [X,X’] este o tăietură s ─ t atunci f[X,X’] = f[X,X’] ─ f[X’,X] este fluxul net peste aceasta tăietură.

Teorema 2.1 (Teorema valorii fluxului pentru problema fluxului minim)

În rețeaua G =(N,A,l,c,s,t) dacă f este un flux de valoare v și [X,X’] este o tăietură s ─ t atunci au loc relațiile:

v = f[X,X’] ≥ ĉ[X,X’].

Demonstrație. Deoarece f etse un flux în rețeaua G, rezultă că f satsface constrângerile

de conservare a fluxului (1.1b). Însumând aceste ecuatii pentru x є X se obține v = f(X,N) ─ f(N,X). Înlocuind N= XX’ în această relație și dezvoltând rezultă că v = f(X,X X’) ─ f(X X’,X) = f(X,X) + f(X,X’) ─ f(X,X) ─ f(X’,X) = f[X,X’]. De asemenea, f satisface constrângerile de mărire a fluxului (2.1c), deci f(X,X’) ≤ l( X,X’) și f(X’,X) ≤ c(X’,X). Re-zultă că v = f[X,X’] = f(X,X’) ─ f(X’,X) ≥ l( X,X’) ─ c(X’,X)=ĉ[X,X’].

▄

Teorema 2.2 (Teorema fluxului minim și a tăieturii maxime)

Dacă există un flux admisibil în rețeaua G = (N,A,l,c,s,t) atunci valoarea fluxului mi-nim de la nodul sursă s la nodul stoc t este egală cu capacitatea tăieturii s ─ t maxime.

Demonstrație. Rezultă din teorema anterioara cã determinerea unui flux admisibil se face în douã moduri:

Etapa 1. Se determinã un flux admisibil.

Etapa 2. Porninid de la un flux admisibil , se determinã un flux minim.

Etapa 1. Folosind teorema admisibilitãții fluxului care are urmatorul enunț: într-o re-țea G = (N,A,l,c) există un flux admisibil dacă și numai dacă pentru orice mulțime XN cu s,t sau s,t este verificată condiția

l(X,X’) ≤ c(X,X’ ) (2.4).

Rezultă că se construiește rețeaua Ğ = (Ñ,Ã,l’,c’), unde Ñ = N, Ã = A{ (s,t), (t,s) }, l’(x,y) = l(x,y), c’(x,y) = c(x,y), (x,y) A, l’(s,t) = l’(t,s) = 0, c’(s,t) = c’(t,s) = ∞. Rezultă că există un flux admisibil în rețeaua G dacă și numai dacă există o circulație admisibilă

în rețeaua Ğ. Conform teoremei admisibilitații circulatiei care ne spune că: într-o rețea Ğ = (Ñ,Ã,l’,c’) există o circulație admisibilă dacă și numai dacă pentru orice mulțime X’ Ñ este verificată condiția

l’(X’”,X’) ≤ c’(X’, X’”) (2.5)

există o circulație admisibilă f” în rețeaua Ğ dacă și numai dacă pentru orice mulțime X’ Ñ este verificată condiția (2.5). Daca s X’ și t X’” sau dacă s X’”, t X’, atunci c(X’, X’”) = ∞ și condiția (2.4) este verificată. Deci (2.4) este verificată pentru ori-ce mulțime X’ Ñ daca și numai dacă este verificată condiția (2.5) pentru orice multime X N cu s,t X sau s,t X’.▄

În continuare voi prezenta algoritmi pentru Etapa 2.

Algoritmi pseudopolinomiali pentru fluxul minim

2.2.1 Algoritmul generic

Fie f un flux de valoare v, L un lanț de la nodul s la nodoul t, cu Llanțul arcelor directe și Lmulțimea arcelor inverse, în rețeaua G = (N,A,l,c,s,t). Un lanț L de la nodul s la no-dul t se numește lanț de micșorare a fluxului (LmF) în raport cu fluxul f dacă f(x,y)>l(x,y) pentru (x,y) Lși f(y,x) < c(y,x) pentru (y,x) L.

Un LmF L în raport cu fluxul f în rețeaua G corespunde unui drum Ð de micșorare a fluxului (DmF) în rețeaua Ĝ (f) și reciproc. Definim capacitatea reziduală a unui LmF L în modul următor:

r(L) = min{ f(x,y) ─ l(x,y) | (x,y) L}, r(L) = min{ c(y,x) ─ f(y,x) | (y,x) L},

r(L) = min{ r(L), r(L) }.

Este evident că r(L) > 0 . Se poate efectua micșorarea de flux: f’(y,x) = f(x,y) ─ r(L), (x,y) L, f’ (y,x) = f(y,x) + r(L), (y,x) L, f’ (x,y) = f(x,y), (x,y) L. Evident fluxul f’ are valoarea v’ = v ─ r(L) .

Teorema 2.3 (Teorema drumului de micșorare a fluxului)

Un flux f este un flux minim dacă și numai dacă rețeaua reziduală Ĝ (f ) ni contine nici un drum de micșorare a fluxului.

Demonstrație. Dacă f este un flux minim atunci în rețeaua reziduală Ĝ(f ) nu există nici un drum de micșorare a fluxului, astfel f nu ar fi un flux minim. Reciproc, dacă re-țeaua reziduală Ĝ(f ) nu conține nici un drum de micșorare a fluxului rezultă că nodul t nu este accesibil din nodul s în Ĝ(f ). Rezultă că [X,X’] este o tăietură s ─ t cu ĉ[X,X’] = v, unde v este valoarea fluxului f . Deci, f este un flux minim.▄

Cât tinp rețeaua reziduală Ĝ(f) contine un DmF putem micșora fluxul de la nodul sursă s la nodul stoc t. Algoritmul generic pentru fluxul minim se bazează pe această proprietate.

includeri de biblioteci și declarări;

void main()

{

se determină fluxul admisibil in rețeaua G;

se determină rețeaua reziduală Ĝ(f);

WHILE (Ĝ(f) conține un DmF )

{

se determină un DmF Ð;

ř(Ð) = min{ř (x,y) | (x,y) Ð};

se efectuează micșorarea de flux;

se actualizează Ĝ(f);

}

}

Algoritmul generic pentru fluxul minim lucrează pe rețeaua reziduală și la terminarea lui, se obțin capacități reziduale optime. Porninid de la aceste capacități reziduale putem determina un flux minim în modul următor: efectuăm schimbările de variabile: c’ (x,y)= c(x,y) ─ l(x,y), ř(x,y) = ř (x,y), f’ (x,y) = f (x,y) ─ l(x,y), (x,y) A. Capacitatea reziduală a arcului (x,y) este

ř (x,y) = c(y,x) ─ f(y,x) + f(x,y) ─ l(x,y)

sau echivalent

ř(x,y) = c’ (x,y) ─ f’ (y,x) + f’ (x,y).

Analog

ř(x,y) = c’ (x,y) ─ f’ (y,x) + f’ (x,y).

Putem determina valorile lui f’ în mai multe moduri. De exemplu,

f’ (x,y) = max{0, ř(x,y) ─ c’ (y,x)} și

f’ (y,x) = max {0, ř(y,x) ─ c’ (x,y)}.

Revenind la variabilele inițiale, obținem

f(x,y) = l(x,y) + max { ř (x,y) ─ c(x,y) + l(y,x), 0} (2.6)

și

f(y,x) = l(y,x) + max { ř(y,x) ─ c(x,y) + l(x,y), 0} (2.6a)

Exemplul 1.1 Fie rețeaua din figura 2.2(a).În figura 2.2(b) este reprezentată rețeaua rezi-duală corespunzătoare fluxului ilustrat în figura 2.2(a). Sedetermină DmF Ð=(1,2,4) a că-

rui capacitate reziduală este ř(Ð) = min {ř(1,2), ř(2,3)} = min{3,6} = 3 și se micșorează cu 3 unități fluxul de-a lungul drumului Ð. Rțeaua reziduală obținută după micșorarea fluxului de-a de-a lundul drumului Ð = (1,2,4) este reprezentată în figura 2.2(c). Se deter-mină unn nou DmF Ð = (1,3,2,4), ř(Ð) = min{ř(1,3)}, ř(3,2), ř(2,4)} = min {6,2,3}= 2 și se micșorează cu două unități fluxul de-a lungul drumului Ð = (1,3,2,4),obtinându-se re-țeaua din figura 2.2(d). Se determină DmF Ð = (1,3,4), ř(Ð) = min{ř(1,3)}, ř(3,4)} = min {4,4}= 4 și după ce se micșorează cu patru unități fluxul de-a lumgul drumului Ð= (1,3,4) se obține rețeaua reziduală reprezentată in figura 2.2(e), în care nu mai există DmF și al-goritmul se termină. Pornind de la capacitățile reziduale optime determinate cu ajutorul algoritmului generic pentru fluxul minim și folosind relațiile (2.6) se determină fluxul mi-nim careeste ilustrat în figura 2.2(f).

Fig 2.2(a)

Fig 2.2(b)

Fig 2.2(c)

Fig 2.2(d)

Fig 2.2(e)

Fig 2.2(f)

Teorema 2.4 (Teorema valorilor întregi). Dacă funcția capacitate c și funcția mar-gine inferioară l sunt cu valori întregi șidacă existăun flux admisibil atunci algoritmul generic pentru fluxul minim converge într-un număr finit de iterații și la terminarea exe-cuției lui se obține un flux minim cu valori întregi.

Demonstrație. Dacă funcția capacitate c și funcția limită inferioară l sunt cu valori în-tregi atunci fluxul admisibil f care este determinat rezolvând o problemă de flux maxim într-o rețea extinsă Ğ = (Ñ,Ã,l’,c’), are valori întregi, conform teoremei valorilor întregi (dacă capacitatea c și fluxul inițial f sunt cu valori întregi atunci algoritmul generic con-verge într-un număr finit de iterații și la terminarea execuției se obține un flux maxim cu valori întregi). Dacă c,l și f sunt cu valori întregi atunci capacitatea reziduală ř(Đ) a oricărui DmF Đ va fi întodeauna o valoare întreagă. Deci, pentru fiecare DmF Đ valoarea fluxului va scădea cu ř(Đ) ≥ 1. Rezultă că după un număr finit de itrații valoarea fluxului va ajunge la valoarea minimă și în rețeaua reziduală nu vor mai exista DmF. Deci, algo-ritmul generic fluxul minim converge într-un număr finit de iterații . Deoarece c,l și f sunt cu valori întregi este evident că după fiecare micșorare de flux, atât fluxul cât și capacita-tea reziduală sunt cu valori întregi. Deci, fluxul minim etse cu valori întregi.▄

Teorema 2.5 Dacă funcția capacitate c, funcția limită inferioară l fluxul admisibil inițal f sunt cu valori întregi, atunci complexitatea algoritmului generic pentru fluxul minim este O(nm).

Demonstrație. La fiecare iterție algoritmul efectuează o micșorare de flux în urma căreia valoarea fluxului scade cu cel puțin o unitate. Complexitatea unei micșorări de flux este O(m), iar numarul de micșorari este O(n), pentru că valoarea fluxului este cuprins între 0 și n. Deci, complexitatea algoritmului generic pentru flux minim este O(nm).▄

Varianta algoritmului Ford-Fulkerson

Varianta algoritmului Ford-Fulkerson este o versiune îmbunătățită a algoritmului generic pentru flux minim. Acest algoritm determină un DmF Đ în rețeaua reziuduală cu ajutorul unui vector n-dimensional numit predecessor și notat cu p. Dacă , pe parcursul executiei algoritmului, un nod xare p(x)0 atunci înseamnă că sa identificat un drum Đ de la nodul s la nodul x în rețeaua reziduală. În plus, pentru fiecare succesor y al lui x către care nu s-a identificat deocamdată un drumcare pornește din nodul s, se poate determina drumul Đ = Đ și se atribuie p(y) = x. Varianta acestui algoritm este următoarea:

(1) includeri de biblioteci și declarări;

void main()

(3) {

(4) se determină fluxul admisibil in rețeaua G;

(5) se determină rețeaua reziduală Ĝ(f);

(6) DO

(7) {

( 8) FOR toate nodurile yŃ

p(y) = 0;

V={s};

WHILE Vø și p(t) = 0

{

se scoate un nod x din V;

FOR fiecare arc (x,y) din Ĝ(f)

IF p(y) = 0 și ys

{

p(y) = x;

V = V {y};

}

}

IF p(t) 0

Micșorare();

}WHILE p(t) = 0;

}

void Micșorare();

{

se determină un DmF cu ajutorul vectorului predecessor p;

se determină ř (Đ) = min{ř(x,y) | (x,y ) Đ};

se efectuează micșorarea de flux de-a lungul drumului Đ;

se actulizează Ĝ(f);

}

Exemplul 2.2 Fie rețeaua din figura 2.3(a). În figura 2.3(b) este reprezentată rețeaua reziduală corespunzătore fluxului admisibil din figura anterioară. La prima iterație vectorul predecesor p poate fi (0,1,1,2). Rezultă că Đ = (1,2,4) cu ř(Đ) = 3. Se micșorează

cu patru unitați fluxul de-a lundul drumului Đ = (1,2,4), iar rețeaua reziduală obținută este prezentată în figura 2.3(c). La a doua iterație vectorul predecesor p este (0,3,1,3), iar DmF este Đ = (1,3,4) cu ř(Đ) = 4. După micșorare se obține rațeaua reziduală din figura 2.3(d).În următoarea iterație se determină vectorul predecesor p (0,3,1,2) , drumul Đ = (1,3,2,4), cu ř(Đ) = 2 și se micșorează cu două unități de-a lungul drumului Đ, obținându-se reziduală reprezentată in figura 2.3(e). În această rețea se inițializează V =(s), se obține V= ø și p(t) = 0 și algoritmul se termină. Pornind de la capacitățile reziduale optime determinate cu ajutorul algoritmului Ford-Fulkerson și folosind relațiile (2.6) sedetermină fluxul minim care este ilustrat în figura 2.3(f).

Fig 2.3(a)

Fig 2.3(b)

Fig 2.3(c)

Fig 2.3(d)

Fig2.3(e)

Fig 2.3(f)

Teorema 2.6 Varianta algoritmului Ford-Fulkerson determină un flux minim de la nodul sursă s la nodul stoc t.

Demonstrație. Execuția algoritmului se termină atunci când nodului stoc t nu I se mai poate atribui un predecesor nenul.

Fie X = { x N | p(x) 0} {s} șiX’ = N \ X. Evident că [X,X’] este o tăietură s ─ t. Deoarece p(x’) = 0 pentru oricare x’ X’ rezultă că ř(x,x’) = 0 pentru orice arc (x,x’) (X,X’). Dar ř(x,x’) = c(x,x’) ─ f(x’,x) + f(x,x’) ─ l(x,x’), c(x,x’) ─ f(x’,x) ≥ 0, f(x,x’) ─ l(x,x’) ≥ 0 și condiția ř(x,x’) = 0 implică faptul că f(x,x’) = l(x,x’) pentru orice arc (x,x’) (X,X’) și f(x’,x) = c(x’,x) pentru orice arc (x’,x) (X’, X). Řezultă că v = f [X,X’] = f(X, X’) ─ f(X’, X) = l(X, X’) ─ c(X’, X) = ĉ[X,X’], adică fluxul f de valoare v obtinut la terminarea algoritmului este un flux minim.▄

Teorema 2.7 Dacă funcția capacitate c,funcția margine inferioară l și fluxul admisinil inițial f sunt cu valori întregi, atunci varianta algoritmului Ford-Fulkerson pentru fluxul minim are complexitatea O(nm).

Demonstrație. La fiecare iterație efectuează o micșorare de flux în urma căreia valoarea fluxului scade cu cel puțin o unitate. Cum valoarea fluxului este cuprinsă între 0 și n, rezultă că algoritmul efectuează O(n) iterații . Deoarece pentru determinarea unui DmF sunt necesare cel puțin m examinări de arce, rezultă că complaxitatea unei iterații este O(m), iar complexitatea allgoritmului este O(nm).▄

Algoritmi polinomiali pentru fluxul minim

Noțiuni introductive

Definiția 2.1 Într-o retea reziduală Ĝ(f) = (Ň,Ǎ,ř) o funcție d : Ň N se numește funcție distanță. Funcția distanță d se numește validă dacă satieface următoarele două condiții:

d(s) = 0 (2.7)

d(y) ≤ d(x) + 1, (x,y) Ǎ (2.8)

Valoarea d(x) se numește etichetă distanță a nodului x, iar condițiile (2.7) și (2.8) se numesc condiții de validitate.

Proprietatea 2.1 (a) Dacă etichetetle distanța sunt valide, atunci eticheta distanță d(x) este o margine inferioară pentru lungimea drumului cel mai scurt de la nodul s la nodul x in rețeaua reziduală Ĝ(f).

(b) Dacă d(t) ≥ n atunci în rețeaua reziduală Ĝ(f) nu există drum de la nodul sursă s la nodul stoc t.

Demonstrație. (a) Fie D = (x ,x ,. . . ,x ,x ) cu x = s, x = x un drum oarecare de lungime k de la nodul s la nodul x în rețeaua reziduală. Condițiile de validitate implică faptul că:

d(x ) ≤ d(x ) + 1 = d(s) + 1 = 1

d(x ) ≤ d(x ) +1 ≤ 2

. . .

d(x) ≤ d(x) + 1 ≤ k.

Deci d(x) = d(x) ≤ k, ceea ce demonstrează prima parte a proprietații.

(b) Eticheta distanță d(t) este o margine inferioară pentru lungimea drumului celui mai scurt de la nodul s la nodul t în rețeaua reziduală Ĝ(f) . Orice drum elementar de la s la t are lungimea cel mult n ─ 1. Deci, dacă d(t) ≥ n atunci in rețeaua reziduală Ĝ(f) nu există drum de la nodul s la nodul t.▄

Definiția 2.2 Etichetele distanță se numesc exacte dacă pentru fiecare nod x, d(x) este egală cu lungimea drumului celui mai scurt de la nodul s la nodul x în rețeaua reziduală Ĝ(f).

Etichetele distanță exacte se pot determina cu ajutorul algoritmului de parcugere BF (în lățime) aplicat rețelei reziduale Ĝ(f) plecân de la nodul sursă s.

Definiția 2.3 Un arc(x,y) din rețeaua reziduală Ĝ(f) se numește admisibil dacă satisface condiția d(y) = d(x) +1; în caz contrar arcul (x,y) se numește inadmisibil. Un drum dela nodul sursă s la nodul stoc t în rețeaua reziduală Ĝ(f) se numește drum admisibil dacă este format doar din arce admisibile, altefel se numeste inadmisibil.

Proprietatea 2.2 În rețeaua reziduală Ĝ(f) un drum admisibil de la nodul sursă s la nodul stoc t este un cel mai scurt drum de micșorare a fluxului.

Demonstrație. Deoarece fiecare arc (x,y) dintr-un drum admisibil D este admisibil, capacitatea reziduală ř(x,y) și etichetele distață d(x) și d(y) îndeplinesc următoarele condiții: (1) ř(x,y) >0 și (2) d(y) = d(x) +1. Condiția (1) implică faptul că D etse un drum de micșorare a fluxului, iar condiția (2) implică faptul că dacă D conține k arce atunci d(t) = k. Deoarece d(t) este o margine inferioară pentru lungimea drumului celui mai scurt de la nodul sursă s la nodul stoc t în rețeaua reziduală Ĝ(f), rezultă că D trebuie sa fie cel mai scurt drum de micșorare a fluxului.▄

Algoritmi polinomiali cu drumuri de micșorare

Algoritmii pseudopolinomiali cu drumuri de micșorare prezentați în paragraful 2.2 au fost obiținuți din algoritmii penru fluxul maxim în modul următor: s-a construit rețeaua reziduală Ĝ(f) pentru problema fluxului minim în locul rețelei reziduale Ğ(f) pentru problema fluxului maxim, s-au determinat drumuri de la nodul sursă s la nodul stoc t în Ĝ(f) după aceleași reguli după care se determină drumuri de la s la t în Ğ(f) în algoritmii corespunzători pentru fluxul maxim și s-a micșorat fluxul de-a lungul acestor drumuri. Această transformare poate fi aplicată oricărui algoritm cu drumuri de mărire pentru fluxul maxim, obținându-se astfel un algoritm similar pentru fluxul minim, care va avea aceeași complexitate ca algoritmul pentru fluxul maxim din care a fost obținut. Algoritmii plinomiali cu drumuri de mărire care calculează fluxul maxim sunt prezenți în următorul tabel.

Tabelul 2.1

Definiția 2.4 În rețeaua reziduală, un drum de la un nod oarecare x la nodul stoc t format doar din arce admisibile se numește drum parțial admisibil, iar nodul x se numește nod current.

În continuare vom prezenta varianta algoritmului Ahuja-Orlin(AODS) al drumului celui mai scurt. Acest algoritm folosește etichetele de distanță exacte și micșorează fluxul de-a lungul drumurilor admisibile.

(1) includeri de biblioteci și declarări;

(2) void main()

(3) {

(4) se determină fluxul admisibil in rețeaua G;

(5) se determină rețeaua reziduală Ĝ(f);

(6) se calculează etichetele distanță exacte d(.) în Ĝ(f);

(7) y = t;

(8) WHILE d(t) < n

(9) {

(10) IF există arc admisibil (x,y)

(11) {

(12) înaintare (x,y);

(13) IF y = s

(14) {

(15) micșorare();

(16) y = t;

(17) }

(18) }

(19) ELSE înapoiere(y);

(20) }

(21) }

(22) int înaintare(x,y);

(23) {

(24) ũ(x) = y;

(25) y = x

(26) }

(27) void înapoiere(y);

(28) {

(29) d(y) = min{ d(x) | (x,y) A} + 1;

(30) IF y t;

(31) y = ũ(y);

(32) }

(33) void micșorare();

(34) {

(35) se determină un DmF Đ utilizând vectoru successor ũ;

(36) se determină g(Đ) = min {ř(x,y) | (x,y) Đ};

(37) se execută micșorarea de flux;

(38) se actualizează rețeaua reziduală Ĝ(f);

(39) }

Algoritmul menține un drum parțial admisibil memorat cu ajutorul vectorului succeso ũ și execută operații de înaintare sau înapoiere de la nodul current y. Dacă nodul curent y este extremitatea finală a unui arc admisibil (x,y) atunci se execută o operație de înaintare: se adaugă arcul (x,y) la începutul drumului parțial admisibil și se reține prin ũ(x) = y, astfel se execută o operație de înapoiere. Operația de înapoiere constă în reetichetarea nodului y, d(y) = min{ d(x) | (x,y) A}+ 1 și eliminarea arcului (y,ũ(y)) din drumul parțial admisibil dacă y t. OperaTiile se repetă până când drumul parțial admisibil devine un drum admisibil și atunci executăm o micșorare de flux. Continuăm acest process până când fluxul devine minim.

Exemplul 2.3 Ilustrăm varianta algoritmului Ahuja-Orlin al drumului celui mai scurt pe rețeaua din figura 2.4(a). În figura 2.4(b) este reprezentată rețeaua reziduala corespunzătoare fluxului adisibil ilustrat in figura anterioară. Pornim de la nodul stoc t =4 cu un drum admisibil parțial vid. Executăm o operație de înaintare și adăugăm nodul (2,4) la drumul parțial admisibil. Memorăm acest drum utilizând vectorul successor ũ, astfel ũ(2) = 4. Acum nodul 2 este nodul current și algoritmul execută o operație de înaintare de la nodul 2. Se efectuează ũ(1) = 2 și se adaugăarcul (1,2) la începutul drumului admisibil parțial, obținându-se drumul admisibil Đ = (1,2,4). Se determină g(Đ)= min { ř(1,2), ř(2,4)} = min {3,4} = 3 și se micșorează cu trei ufluxul de-a lungul drumului Đ = (1,2,4) obținându-se rețeaua reprezentată în figura 2.4(c). Se pleacă din nou de la nodul stoc t = 4 cu un drum parțial admisibil vid. Executăm o operație de înaintare și adăugăm arcul (2,4) la drumul parțial admisibil și efectuăm ũ(2) = 4. Deoarece nodul current, care este 2, nu este extremitatea finală a unui arc admisibil , efectuăm o operație de înapoiere d(2) = min{ d(3), d(4)} +1 =2, nodul current devine nodul ũ(2) = 4 și eliminăm arcul (2,4) din drumul parțial minim. La următoarele iterații, se vor determina drumurile admisibile Đ =(1,3,4), apoi Đ =(1,3,2,4). Rețeaua obținută după micșorarea cu 4 unități de-a lungul drumului Đ =(1,3,4) este reprezentată în figura 2.4(d). După micșorarea cu 2 unități a fluxului de-a lungul drumului Đ = (1,3,2,4) se obține rețeaua reziduală corespunzătoare fluxului minim ilustrat în figura 2.4(e). Pornind de la capacitățile reziduale optime și folosind relațiile (2.6) se determină fluxul minim care este reprezetat în figura 2.4(f).

Teorema 2.8 Varianta algoritmului Ahuja-Orlin al drumului celui mai scurt determinăun flux în rețeaua G = (N,A,l,s,t).

Demonstrație. Algoritmul Ahuja-Orlin al drumului cel mai scurt se termină când d(t) ≥ n. Conform proprietății 2.1 (b) rezultă că rețeaua reziduală nu conține DmF de la nodul sursă s la nodul stoc t . Deci, la terminare, algoritmu; drumului celui mai scurt Ahuja-Orlin determină un flux minim.▄

Fig 2.4(a)

Fig 2.4(b)

Fig 2.4 (c)

Fig 2.4(d)

Fig 2.4(e)

Fig 2.4(f)

Teorema 2.9 Varianta algoritmului Ahuja-Orlin al drumului celui mai scurt are complexitatea O (nm).

Demonstrație. Folosim lema care spune că: dacă algoritmul AODS reetichetează orice nod de cel milt k ori, timpul necesar pentru determinarea arcelor admisibile și reetichetarea nodurilor este O(k| E(x)|) = O(km) și lema care spune: În execuția algoritmului APDS numarul iterațiilor de înapoiere este cel mult n, iar numărul măririlor de flux este cel mult mn/2. Cu ajutorul lemelor, determinarea arcelor admisibile șireetichetarea nodurilor are complexitatea O(mn). Fiecare micșorare de flux are complexitatea O(n). Deci complexitatea micșorărilor de flux este O (nm).Ținând seama

că un drum admisibil are lungimea cel mult n și că numărul operațiilor de înapoiere este O(n) rezultă că numărul de operațiilor de înaintare este O(nm + n). Cum din combinarea acestor margini se reduce nși rezultă complexitatea algoritmului este O(nm).▄

Algoritmi plinomiali cu prefluxuri

Algoritmul preflux generic

Fie f un preflux în rețeaua G = (N,A,c,s,y). Un nod x N \ {s,t} se numește nod active dacă e(x) < 0. Prin convenție nodurile s și t nu sunt active niciodată. Existența nodurilor active indică faptul că prefluxul nu este flux. De aceea, operația de bază a algoritmului constă în a selecta un nod activ și a-I diminua dificitul. Pentru a diminua dificitul unui nod activ se retrage fluxul către nodurile adiacente lui care se găsesc mai “aproape” de nodul sursă. “Apropierea “ nodurilor față de nodul sursă se măsoară cu ajutorl etichetelor distanță exacte. De aceea, se retrage flux doar pe arcele admisibile. În cazul în care nodul active selectat nu este extremitatea finală a nuci unui arc admisibil I se va mări eticheta distanță astfel încât să se creeze cel puțin un arc admisibil. Această mărire a etichetei distanță va fi numită operație de reetichetare. Algoritmul se termină atunci când în rețea nu mai există noduri active, ceea ce înseamnă că prefluxul este de fapt un flux.

Acest algoritm preflux generi pentru fluxul minim este o variantă a algoritmului preflux generic pentru flux maxim.

(1) includeri de biblioteci și declarări;

(2) void main()

(3) {

(4) se determină fluxul admisibil in rețeaua G;

(5) se determină rețeaua reziduală Ĝ(f);

(6) se calculează etichetele distanță exacte d(.) în Ĝ(f);

(7) IF t nu este etichetat;

(8) f este un flux minim;

(9) ELSE

(10) FOR (x,y) E(t)

(11) f(x,t) = l(x,t);

(12) d(t) = n;

(13) WHILE în rețeaua reziduală Ĝ(f) există un arc admisibil (x,y)

(14) se selectează un nod active y;

(15) IF în rețeau reziduală există un arc admisibil (x,y)

(16) se retrag g = min{─e(y),ř(x,y)} unități de flux de la nodul x la nodul y

(17) ELSE

(19) d(y) = min{d(x) | (x,y) Á} + 1;

(20) }

(21) }

(22) }

În exemplul următor vom ilustra algoritmul preflux generic pentru fluxul minim.

Exemplul 2.4 Fie figura 2.5(a), în figura 2.5(b) este reprezentată rețeau reziduală fluxului admisibil ilustrat în figura anterioară. În rețeaua reziduală obținută după inițializările din liniile (10), (11) și (12) și reprezentată înfigura 2.5(c) există două noduri active: 2 și 3. Presupunem că algoritmul selectează nodul active 3. Rezultă că va retrage g= min{─e(3),ř (1,3)} = min {4,6} = 4 unități de flux pe arcul (1,3). În urma acestei operații, nodul 3 nu mai este activ. Apoi algoritmul va selecta singurul nod activ , nodul 2 și va retrage g= min{─e(2),ř (1,2)} = min {6,3} = 3 unități de flux pe arcul admisibil (1,2). Nodul 2 a rămas active și nu este extremitatea finală a nici uni arc admisibil, deci va fi reetichetat: d(2) = min{d(3), d(4)} + 1 = min{1,2} + 1 = 2. Rețeaua reziduală astfel obținută etse reprezentată în figura 2.5(d). Prin operațias de reetichetare s-a creat arcul (3,2), pe care se va retrage g = 2 unitați de flux. Cum nodul 2 este în cuntinuare activ și nu mai există arce admisibile cu extremitatea finală nodul 2, rezultă că va fi reetichetat: d(2) = 5. În rețeau reziduală obținută, care este reprezentată în figura 2.5(e) există două noduri active: 2 și 3. Dacă se selectează din nou nodul 2 se va retrage o unitate de flux pe arcul admisibil (4,2) astfel singurul nod active rămas este 3, deci se vor retrage 2 unități de flux pe arcu admisibil (1,3). Astfel s-a obținut rețeaua din figura 2.5(f), în care nu mai există noduri active și algoritmul se termină. Pornind de la capacitățile reziduale optime obținute cu algoritmul preflux generic pentru fluxul minim și folosind relațiile (2.6) se determionă fluxul minim reprezentat în figura 2.5(g)

Fig 2.5(a)

Fig 2.5(b)

Fig 2.5(c)

Fig 2.5(d)

Fig 2.5(e)

Fig 2.5(f)

Fig 2.5(g)

Teorema 2.10 Algoritmul preflux generic pentru fluxyl minim determină un flux minim în rețeaua G =( N,A,c,s,t).

Demonstrație. Algoritmul se termină atinci când e(x) = 0, x N \ {s,t}, ceea ce implică faptul că f este un flux. Deoarece d(t) ≥ n, în rețeaua reziduală nu există drum de la nodul sursă s la nodul stoc t. Deci, fluxul curent este un flux minim.▄

Spunem că o retragere de flux de la nodul y la nodul x pe arcul (x,y) este completă dacă duce la eliminarea arcului (x,y) din rețeaua reziduală; în caz contrar spunem că este o retragere incompletă.

Teorema 2.11 Complexitatea algoritmului preflux generic pentru fluxul minim este O(nm).

Demonstrație. Analiza complexității algoritmului preflux generic pentru fluxul minim se bazează pe următoarele trei rezultate:

numărul total de iterații de operații de reetichetare este cel mult 2 n.

algoritmul efectuează cel mult nm retrageri de flux.

Algoritmul efectuează O(nm) retrageri incomplete de flux.

Conform următorei leme: algoritmul preflux generic execută O(nm) înaintări saturarte , adică algoritmul executa înaintări până când nu va mai exista noduri active și arce admisibile, deci algoritmul are complexitatea O(nm).

Algoritmul preflux FIFO

La fiecare itrație, algoritmul preflux generic pentru fluxul minim selectează un nod active y și efectuează fie o retragere de flux completă, fie o retregere incompletă, fie o reetichetare a nodului y . Dacă se efectueazăo retragere de flux completă, atunci nodul x potă să rămână active, dar nu este obligatoriu ca algoritmul să-l selecteze din nou la iterația următoare. Algoritmul preflux FIFO lucreaza după următoarea regulă: un nod y este selectat la iterații conecutive pă când e(y) = 0 sau y reetichetat. În consecință, algoritmul preflux FIFO pentru fluxul minim va executa mai multe retrageri complete de la nodul y , urmate fie de retragere incompletă (e(y) devine 0), fie de o operție de reetichetare (nu există arc admisibil (x,y)). Numim această secvență de operații examinarea nodului y.

Notăm cu L lista nodurilor active. Algoritmul prflux FIFO pentru fluxul minim examinează nodurile active în ordinea primului iterat,primul ieșit (FIFO). Deci, lista nodurilor active L va fi organizată ca o coadă. Algoritmul se termină când coada nodurilor ative dvine vidă.

includeri de biblioteci și declarări;

void main()

{

Se determină fluxul admisibil în rețeaua G;

Se determină rețeaua reziduală Ĝ(f);

Se calculeaza etichetele distanță exacte d(.) în rețeaua reziduala Ĝ(f);

IF t nu este etichetat

Scrie f este un flux minim;

ELSE

{

L = ø;

FOR (x,y) E(t)

{

f (x,y) = l (x,y);

IF e(x) < 0 și x s;

Se adaugă x în vârful cozii L;

}

d(t) = n;

WHILE L ø

{

Se scoate primul nod y din L;

Retragere/reetichetare(y);

}

}

}

void retragere/reetichetare (y)

{

Se selectează primul arc (x,y) cu extremitatea finală y dinĜ(f);

B = 1;

DO

{

IF (x,y) este arc admisibil

{

Se retrag g = min {-e(y), ř(x,y)} unități de flux de la nodul y la nodul x;

IF x L și xs și xt

Se adaugă x în vârfu cozii L;

}

IF e(y) < 0

IF (x,y) nu este ultimul arc cu extremitatea finală y din Ĝ(f);

Se selectează selecteaza urmatorul arc extremitatea finală y din Ĝ(f);

ELSE

{

d(y) = min { d(x) | (x,y) Á} + 1;

B = 0;

}

} WHILE e(y) = 0 sau B = 0

IF e(y) < 0

Se adaugă y în vârful cozii L;

}

Exemplul 2.5 Ilustrăm algoritmul preflux FIFO pentru fluxul minim pa rețeaua din figura 2.6(a), în care este ilustrat și un flux admisibil. După inițializările din liniile (12) ─ (18) se obține rețeau reziduală din figura 2.6(b) și L = {2,3} și îl examinează: retrage 3 unități de flux pe arcul admisibil (1,2), iar apoi , pentru că nu mai există arce admisicile cu extremitatea inală 2 îl reeticheteză și îl adaugă la sfârșitul cozii L. Deci, L = {3,2}, iar rețeaua reziduală este reprezentată în figura 2.6(c). Apoi algoritmul scoate nodul 3 din coada L și-l examinează retrăgând 4 unități de flux pe arcul (1,3). Astfel nodul 3 nu mai este activ , iar L={2}. Rețeaua reziduală obținută după examinarea nodului 3 este reprezentată în figura 2.6(d). În continuare algoritmul scoate din coada L nodul 2, retrage 2 unități de flux pe arcul (3,2), adaugă nodul 3 în coada L pentru că a redevenit activ, reetichetează nondul 2; d(2) = 5 și-l adaugă la sfârșitul cozii L. Dupa examinare nodului 2 se obține rețeraua reziduală din figura 2.6(e), iar L = {3,2}. Apoi algoritmul scote nodul 3 din coada L și-l examinează. Se retrag 2 unități de flux pe arcul admisibil (1,3) și nodul 3 nu mai este activ. Rețeaua reziduală astfel obținută este reprezentată în figura 2.6(f). Algoritmul va scoate nodul 2 din coadă și va retrage o unitate de flux pe arcul admisibil (4,2). Astfel nodul 2 nu mai este activ , L = ø și algoritmul se termină. Pornind de la capacităție reziduale optime cu algoritmul preflux FIFO pentru fluxul minim, care sunt illustrate în figura 2.6(g) și apoi se determină fluxul minim din figura 2.6(h) cu ajutorul relațiilor (2.6).

Fig 2.6(a)

Fig 2.6(b)

Fig 2.6(c)

Fig 2.6(d)

Fig 2.6(e)

Fig 2.6(f)

Fig 2.6.(g)

Fig 2.6(h)

Teorema 2.12 Algoritmul preflux FIFO pentru fluxul minim determină un flux minim în rețeaua G = (N,A,c,s,t).

Demonstrație. Algoritmul se termină atunci când coada L este vidă, iar acest lucru ne spune că și e(x) = 0 ceea ce implică faptul că există un flux. Deoarece d(t) ≥ n, în rețeaua reziduală nu există drum de la nodul sursă s la nodul stoc t, deci, fluxul curent este un flux minim.▄

Teorema 2.13 Complexitatea algoritmului preflux FIFO pentru fluxul minim este O(n).

Algoritmul preflux cu eticheta cea mai mare

Algoritmul preflux cu eticheta cea mai mare pentru fluxul minim retrage întotdeauna fluxul de la nodul active y cu eticheta cea mai mare. Fie p = max {d(t) | x este nod activ }. Algoritmul examinează mai întâi nodurile cu etichetele distanț egale cu p – 1. Appoi de la aceste noduri retrage fluxul la nodurile care au etichetele distantă egale cu p – 2 și așa mai departe până când fie algoritmul reetichetează un nod, fie a epuizat toate nodurile active. După reetichetarea unui nod, algoritmul repeat acelaș procedeu. Dacă algoritmul nu efectuează nici o reetichetare pe parcursul a n examinări successive de noduri atunci tot deficitul ajunge în nodul sursă sau înapoi în nodul stoc și algoritmul se termină.

Algoritmul preflux cu eticheta cea mai mare pentru fluxul minim poate fi implementat ușor dacă în algoritmul preflux FIFO pentru fluxul minim lista L a nodurilor active nu este organizată ca o coadă obișnuită, ci ca o coadă prioritară cu prioritatea funcția distanță d.

(1) includeri de biblioteci și declarări;

(2) void main()

(3) {

(4) Se determină fluxul admisibil în rețeaua G;

(5) Se determină rețeaua reziduală Ĝ(f);

(6) Se calculeaza etichetele distanță exacte d(.) în rețeaua reziduala Ĝ(f);

(7) IF t nu este etichetat

(8) Scrie f este un flux minim;

(9) ELSE

(10) {

(11) L = ø;

(12) FOR (x,y) E(t)

(13) {

(14) f (x,y) = l (x,y);

(15) IF e(x) < 0 și x s;

(16) Se adaugă x în coada L având prioritatea d(x);

(17) }

(18) d(t) = n;

(19) WHILE L ø

(20) {

(21) Se scoate primul nod y din L având prioritatea cea mai mare;

(22) Retragere/reetichetare(y);

(23) }

(24) }

(25) }

(26) void retragere/reetichetare (y)

{

arcul curent este primul arc din Ĕ(y);

B = 1;

DO

{

Fie (x,y) arcul curent din Ĕ(y);

IF (x,y) este arc admisibil

{

Se retrag g = min {-e(y), ř(x,y)} unități de flux de la nodul y la nodul x;

IF x L și xs și xt

Se adaugă x în coada L având prioritatea d(x);

}

IF e(y) < 0

IF (x,y) nu este ultimul arc din Ĕ(y);

Arcul curent este următorul arc din Ĕ(y);;

ELSE

{

d(y) = min { d(x) | (x,y) Á} + 1;

B = 0;

}

} WHILE e(y) = 0 sau B = 0

IF e(y) < 0

Se adaugă y în coada L având prioritatea d(y);

}

Teorema 2.13 Dacă exista un flux admisibil în rețeaua G , atunci algoritmul preflux cu eticheta cea mai mare pentru fluxul minim determină un flux minim în rețeaua G = (N,A,c,s,t), iar complexitatea acestui algoritm este O(nm).

Demonstrație. Algoritmul se termină atunci când coada L este vidă, iar acest lucru ne spune că și e(x) = 0 ceea ce implică faptul că există un flux. Deoarece d(t) ≥ n, în rețeaua reziduală nu există drum de la nodul sursă s la nodul stoc t, deci, fluxul curent este un flux minim.▄

Fig 2.7(a)

Fig 2.7(b)

Fig 2.7(c)

Fig 2.7(d)

Fig 2.7(e)

Fig 2.7(f)

Fig 2.7(g)

Bibliografie generală

Ciurea E., Ciupală L., Aldoritmi.Introducere în algoritmica fluxurilor în rețele , Editura Tehnică București 2001

Ahuja R.K., Magnati T.L., Orlin I.B., Network flows.Theoty algoritms and application, Prentice Hall, Englewood cliffs, new Jersey 1993

Bang-Jensen J., Gutin G., Digraphs.Theory algoritms and application, Spring-Verlang, London 2001

Ciurea E., Algoritmi.Introducere în algoritmica grafurlor Editura Tehnică București 2001

Croitoru C., Tehnici de bază în optimizarea combinatorică Editura Universității “ Alexandru Ioan Cuza” Iași 1992

Tomescu Ioan Probleme de combinatorică șiTeoria grafurilor Editura Didactică și Pedagogică București 1985

Tudor Sorin Informatică Editura L&S Info-Mate București 2005

ANEXA 1

//Programul Generic

#include<fstream.h>

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

int n;

int a[100][100];

void main()

{

int i,j;

int r[100][100];

int l[100][100],c[100][100];

clrscr();

fstream h("exa.in",ios::in);

fstream z("exl.in",ios::in);

fstream y("exc.in",ios::in);

h>>n;

int li,ci;

z>>li;

y>>ci;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

h>>a[i][j];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

z>>l[i][j];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

y>>c[i][j];

h.close();

z.close();

y.close();

for(i=1;i<=n;i++)

a[n][1]=1;

c[n][1]=32000;

l[n][1]=0;

/*/ int r[100][100];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

r[i][j]=0;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][j]==1)

r[i][j]=r[i][j]+c[i][j]-l[i][j];*/

int v[100];

int s1[100];

int s2[100];

for(i=1;i<=n;i++)

{

s1[i]=0;

s2[i]=0;

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if((a[i][j]==1)&&(a[j][i]==0))

{

s1[i]=s1[i]+l[i][j];

s2[i]=s2[i]+l[j][i];

}

else

if((a[i][j]==1)&&(a[j][i]==1))

{

s2[i]=s2[i]+l[j][i];

s1[i]=s1[i]+l[i][j];

}

else

s2[i]=s2[i]+l[j][i];

for(i=1;i<=n;i++)

v[i]=s2[i]-s1[i];

/* for(i=1;i<=n;i++)

cout<<" "<<v[i]; //afisez valorile nodurilor*/

int m;

m=n+2;

int g[120][120];

for(i=1;i<=m;i++)

for(j=1;j<=m;j++)

g[i][j]=0;

for(i=2;i<=m-1;i++)

for(j=2;j<=m-1;j++)

g[i][j]=a[i-1][j-1];

for(i=1;i<=n;i++)

if(v[i]<0)

g[i+1][1]=1;

else

g[m][i+1]=1;

/* for(i=1;i<=m;i++)

{

for(j=1;j<=m;j++)

cout<<" "<<g[i][j]; //afisez matricea extinsa.

cout<<endl;

} */

int cap[120][120];

for(i=2;i<=m-1;i++)

for(j=2;j<=m-1;j++)

cap[i][j]=c[i-1][j-1]-l[i-1][j-1];

for(i=1;i<=n;i++)

if(v[i]<0)

cap[i+1][1]=-v[i];

else

cap[m][i+1]=v[i];

/* for(i=1;i<=m;i++)

{

for(j=1;j<=m;j++)

cout<<" "<<cap[i][j]; //afisez cap rez a matricii extinse

cout<<endl;

} */

int v1[120];

for(i=2;i<=m-1;i++)

v1[i]=v[i-1];

v1[1]=0; v1[m]=0;

int N[100]; int b;

fstream of("nod.in",ios::in);

of>>b;

for(i=1;i<=b;i++)

of>>N[i];

int u[100]; int viz[100];

int w[100]; int d[100];

int p[100];

int k,be,s,t;

s=N[1];

be=1;

viz[1]=s;

for(i=2;i<=n;i++)

viz[i]=0;

for(i=2;i<=n;i++)

u[i-1]=N[i];

t=1;

p[s]=0;

for(i=2;i<=n;i++)

p[i]=0;

d[s]=0;

for(i=2;i<=n;i++)

d[i]=32000;

k=0;

int mi;

while(be!=0)

{ for(i=1;i<=be;i++)

mi=viz[i];

for(j=2;j<=n;j++)

// for(i=1;i<=n;i++)

if(a[mi][j]==1)

for(i=1;i<=n-1;i++)

if(j==u[i])

{

for(i=t;i<=n-1;i++)

u[i]=u[i+1];

t=t-1;

be++;

for(i=j;i<=j;i++)

viz[i]=j;

p[j]=mi;

d[j]=d[mi]+1;

}

be=be-1;

k=k+1;

w[k]=mi;

}

/* for(i=1;i<=n;i++)

cout<<p[i]; //afisez predecsorii */

int fi[120][120];

for(i=1;i<=m;i++)

for(j=1;j<=m;j++)

fi[i][j]=0;

for(i=m;i>=1;i–)

for(j=m;j>=1;j–)

if(g[i][j]==1)

if(cap[i][j]>=cap[j][p[i]])

if(v1[j]<0)

fi[i][j]=fi[i][j]-v1[j];

else

fi[i][j]=fi[i][j]+v1[j];

else

if(v1[j]<0)

fi[j][p[j]]=fi[j][p[j]]-v1[j];

else

fi[j][p[j]]=fi[j][p[j]]+v1[j];

a[n][1]=0;

for(i=2;i<=m-1;i++)

for(j=2;j<=m-1;j++)

if(g[i][j]==1)

fi[i-1][j-1]=fi[i][j];

int f[100][100];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

f[i][j]=0;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][j]==1)

r[i][j]=c[j][i]-fi[j][i]+fi[i][j]-l[i][j];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

while(j<=n)

{

int min[100];

for(i=1;i<=n;i++)

min[i]=32000;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if((a[i][j]==1)&&(r[i][j]<min[i]))

min[i]=r[i][j];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(i==p[j])

r[i][j]=r[i][j]-min[i];

int max=0;

int sum[100];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][j]==1)

sum[i]=r[i][j]-c[j][i]+l[j][i];

else

if(a[j][i]==1)

sum[j]=r[j][i]-c[i][j]+l[i][j];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][j]==1)

if(max<sum[i])

f[i][j]=l[i][j]+sum[i];

else

f[i][j]=l[i][j]+max;

else

if(a[j][i]==1)

if(max<sum[j])

f[j][i]=l[j][i]+sum[j];

else

f[j][i]=l[j][i]+max;

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

cout<<" "<<f[i][j];

cout<<endl;

}

}

}

ANEXA 2

// Programul Ford-Fulkerson

#include<fstream.h>

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

int n;

int a[100][100];

//int c[100][100],l[100][100];

void micsorare()

{

int i,j,li,ci;

int r[100][100];

int l[100][100],c[100][100];

// clrscr();

fstream h("exa.in",ios::in);

fstream z("exl.in",ios::in);

fstream y("exc.in",ios::in);

h>>n;

z>>li;

y>>ci;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

h>>a[i][j];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

z>>l[i][j];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

y>>c[i][j];

h.close();

z.close();

y.close();

int b;

int N[100];

fstream of("nod.in",ios::in);

of>>b;

for(i=1;i<=b;i++)

of>>N[i];

int u[100]; int viz[100];

int w[100]; int d[100];

int p[100]; int f[100][100];

int k,be,s,t;

s=N[1];

be=1;

viz[1]=s;

for(i=2;i<=n;i++)

viz[i]=0;

for(i=2;i<=n;i++)

u[i-1]=N[i];

t=1;

p[s]=0;

for(i=2;i<=n;i++)

p[i]=0;

d[s]=0;

for(i=2;i<=n;i++)

d[i]=32000;

k=0;

int mi;

while(be!=0)

{ for(i=1;i<=be;i++)

mi=viz[i];

for(j=2;j<=n;j++)

// for(i=1;i<=n;i++)

if(a[mi][j]==1)

for(i=1;i<=n-1;i++)

if(j==u[i])

{

for(i=t;i<=n-1;i++)

u[i]=u[i+1];

t=t-1;

be++;

for(i=j;i<=j;i++)

viz[i]=j;

p[j]=mi;

d[j]=d[mi]+1;

}

be=be-1;

k=k+1;

w[k]=mi;

}

/* for(i=1;i<=n;i++)

cout<<p[i];*/

int fi[120][120];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][j]==1)

r[i][j]=c[j][i]-f[j][i]+f[i][j]-l[i][j];

int min;

min=32000;

for(i=n;i>=1;i–)

//for(j=n;j>=1;j–)

if((r[i][p[i]]<min)&&(a[i][p[i]]==1))

min=r[i][p[i]];

for(i=n;i>=1;i–)

for(j=n;j>=1;j–)

if(a[i][p[j]]==1)

if(i==p[j])

r[i][p[j]]=r[i][p[j]]-min;

int max=0;

int sum[100];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][j]==1)

{

sum[i]=r[i][j]-c[j][i]+l[j][i];

if(max<sum[i])

f[i][j]=l[i][j]+sum[i];

else

f[i][j]=l[i][j]+max;

}

else

if(a[j][i]==1)

{

sum[j]=r[j][i]-c[i][j]+l[i][j];

if(max<=sum[j])

f[j][i]=l[j][i]+sum[j];

else

f[j][i]=l[j][i]+max;

}

a[n][1]=0;

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

cout<<" "<<f[i][j];

cout<<endl;

}

}

void main()

{

int i,j,li,ci;

int r[100][100];

int l[100][100],c[100][100];

clrscr();

fstream h("exa.in",ios::in);

fstream z("exl.in",ios::in);

fstream y("exc.in",ios::in);

h>>n;

z>>li;

y>>ci;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

h>>a[i][j];

for(i=1;i<=li;i++)

for(j=1;j<=li;j++)

z>>l[i][j];

for(i=1;i<=ci;i++)

for(j=1;j<=ci;j++)

y>>c[i][j];

h.close();

z.close();

y.close();

for(i=1;i<=n;i++)

a[n][1]=1;

c[n][1]=32000;

l[n][1]=0;

int v[100];

int s1[100];

int s2[100];

for(i=1;i<=n;i++)

{

s1[i]=0;

s2[i]=0;

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if((a[i][j]==1)&&(a[j][i]==0))

{

s1[i]=s1[i]+l[i][j];

s2[i]=s2[i]+l[j][i];

}

else

if((a[i][j]==1)&&(a[j][i]==1))

{

s2[i]=s2[i]+l[j][i];

s1[i]=s1[i]+l[i][j];

}

else

s2[i]=s2[i]+l[j][i];

for(i=1;i<=n;i++)

v[i]=s2[i]-s1[i];

/* for(i=1;i<=n;i++)

cout<<" "<<v[i]; //afisez valorile nodurilor*/

int m;

m=n+2;

int g[120][120];

for(i=1;i<=m;i++)

for(j=1;j<=m;j++)

g[i][j]=0;

for(i=2;i<=m-1;i++)

for(j=2;j<=m-1;j++)

g[i][j]=a[i-1][j-1];

for(i=1;i<=n;i++)

if(v[i]<0)

g[i+1][1]=1;

else

g[m][i+1]=1;

/* for(i=1;i<=m;i++)

{

for(j=1;j<=m;j++)

cout<<" "<<g[i][j]; //afisez matricea extinsa.

cout<<endl;

} */

int cap[120][120];

for(i=2;i<=m-1;i++)

for(j=2;j<=m-1;j++)

cap[i][j]=r[i-1][j-1];

for(i=1;i<=n;i++)

if(v[i]<0)

cap[i+1][1]=-v[i];

else

cap[m][i+1]=v[i];

/* for(i=1;i<=m;i++)

{

for(j=1;j<=m;j++)

cout<<" "<<cap[i][j]; //afisez cap rez a matricii extinse

cout<<endl;

} */

int v1[120];

for(i=2;i<=m-1;i++)

v1[i]=v[i-1];

v1[1]=0; v1[m]=0;

int N[100];int b;

fstream of("nod.in",ios::in);

of>>b;

for(i=1;i<=b;i++)

of>>N[i];

int u[100]; int viz[100];

int w[100]; int d[100];

int p[100];

int k,be,s,t;

s=N[1];

be=1;

viz[1]=s;

for(i=2;i<=n;i++)

viz[i]=0;

for(i=2;i<=n;i++)

u[i-1]=N[i];

t=1;

p[s]=0;

for(i=2;i<=n;i++)

p[i]=0;

d[s]=0;

for(i=2;i<=n;i++)

d[i]=32000;

k=0;

int mi;

while(be!=0)

{ for(i=1;i<=be;i++)

mi=viz[i];

for(j=2;j<=n;j++)

if(a[mi][j]==1)

for(i=1;i<=n-1;i++)

if(j==u[i])

{

for(i=t;i<=n-1;i++)

u[i]=u[i+1];

t=t-1;

be++;

for(i=j;i<=j;i++)

viz[i]=j;

p[j]=mi;

d[j]=d[mi]+1;

}

be=be-1;

k=k+1;

w[k]=mi;

}

/* for(i=1;i<=n;i++) //afisez predecesorii.

cout<<p[i];*/

int fi[120][120];

for(i=1;i<=m;i++)

for(j=1;j<=m;j++)

fi[i][j]=0;

for(i=m;i>=1;i–)

for(j=m;j>=1;j–)

if(g[i][j]==1)

if(cap[i][j]>=cap[j][p[i]])

if(v1[j]<0)

fi[i][j]=fi[i][j]-v1[j];

else

fi[i][j]=fi[i][j]+v1[j];

else

if(v1[j]<0)

fi[j][p[j]]=fi[j][p[j]]-v1[j];

else

fi[j][p[j]]=fi[j][p[j]]+v1[j];

a[n][1]=0;

int f[100][100];

for(i=2;i<=m-1;i++)

for(j=2;j<=m-1;j++)

if(g[i][j]==1)

f[i-1][j-1]=fi[i][j];

do

{

int wi[100]; int x;

int p[100];

for(j=1;j<=n;j++)

p[j]=0;

wi[1]=1;

while((wi[1]!=0)&&(p[n]==0))

{

/*for(i=1;i<=n;i++)

if(wi[i]!=0)

{

x=wi[i];

wi[i]=0;

// i++;

}*/x=wi[1];

wi[1]=0;

// for(i=x;i<=n;i++)

for(j=1;j<=n;j++)

if(a[x][j]==1)

if((p[j]==0)&&(j!=1))

{

p[j]=i;

for(i=1;i<=n;i++)

if(j!=wi[i])

wi[i]=j;

}

}

if(p[n]!=0)

micsorare();

}while(p[n]==0);

}

Anexa 3

//Algoritmul preflux generic

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

#include<math.h>

int n,i,j;

int a[100][100];

int l[100][100];c[100][100];

void main()

{

int r[100][100];

int f[100][100];

clrscr();

cout<<"n=";

cin>>n;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

cout<<"a["<<i<<"]"<<"["<<j<<"]=";

cin>>a[i][j];

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][j]==1)

{

cout<<"l["<<i<<"]"<<"["<<j<<"]=";

cin>>l[i][j];

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][j]==1)

{

cout<<"c["<<i<<"]"<<"["<<j<<"]=";

cin>>c[i][j];

}

a[n][1]=1;

c[n][1]=32000;

l[n][1]=0;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][j]==1)

r[i][j]=c[i][j]-l[i][j];

int v[100];

int s1[100];

int s2[100];

for(i=1;i<=n;i++)

{

s1[i]=0;

s2[i]=0;

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if((a[i][j]==1)&&(a[j][i]==0))

{

s1[i]=s1[i]+l[i][j];

s2[i]=s2[i]+l[j][i];

}

else

if((a[i][j]==1)&&(a[j][i]==1))

{

s2[i]=s2[i]+l[j][i];

s1[i]=s1[i]+l[i][j];

}

else

s2[i]=s2[i]+l[j][i];

for(i=1;i<=n;i++)

v[i]=s2[i]-s1[i];

int m;

m=n+2;

int g[120][120];

for(i=2;i<=m-1;i++)

for(j=2;j<=m-1;j++)

g[i][j]=a[i-1][j-1];

for(i=1;i<=n;i++)

if(v[i]<0)

g[i+1][1]=1;

else

g[m][i+1]=1;

int cap[120][120];

for(i=2;i<=m-1;i++)

for(j=2;j<=m-1;j++)

cap[i][j]=c[i-1][j-1]-l[i-1][j-1];

for(i=1;i<=n;i++)

if(v[i]<0)

cap[i+1][1]=-v[i];

else

cap[m][i+1]=v[i];

int v1[120];

for(i=2;i<=m-1;i++)

v1[i]=v[i-1];

v1[1]=0; v1[m]=0;

int p[120];

for(i=1;i<=m;i++)

for(j=1;j<=m;j++)

if((g[i][j]==1)&&(cap[i][j]>=cap[i][j++]))

p[j]=i;

for(i=m;i>=1;i–)

for(j=m;j>=1;j–)

if(g[i][j]==1)

if(cap[i][j]>=cap[j][p[j]])

if(v1[j]<0)

f[i][j]=f[i][j]-v1[j];

else

f[i][j]=f[i][j]+v1[j];

else

if(v1[j]<0)

f[j][p[j]]=f[j][p[j]]-v1[j];

else

f[j][p[j]]=f[j][p[j]]+v1[j];

a[n][1]=0;

for(i=2;i<=m-1;i++)

for(j=2;j<=m-1;j++)

if(g[i][j]==1)

f[i-1][j-1]=f[i][j];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][j]==1)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

r[i][j]=c[j][i]-f[j][i]+f[i][j]-l[i][j];

int d[100];

for(i=1;i<=n;i++)

d[i]=0;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][j]==1)

p[j]=i;

for(j=1;j<=n;j++)

if(a[1][j]==1)

d[j]=1;

else

d[j]=2;

int e[100];

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if((a[i][j]==1)&&(a[j][i]==0))

{

s1[i]=s1[i]+f[i][j];

s2[i]=s2[i]+f[j][i];

}

else

if((a[i][j]==1)&&(a[j][i]==1))

{

s2[i]=s2[i]+f[j][i];

s1[i]=s1[i]+f[i][j];

}

else

s2[i]=s2[i]+f[j][i];

for(j=1;j<=n;j++)

if(a[1][j]==1)

e[1]=s2[1]-s1[1];

for(i=1;i<=n;i++)

if(a[i][n]==1)

e[n]=s2[n]-s1[n];

for(i=2;i<=n;i++)

for(j=1;j<n;j++)

if(a[i][j]==1)

e[i]=s2[i]-s1[i];

if(d[n]!=n)

cout<<"f este un flux minim";

else

{

for(i=1;i<=n;i++)

if(a[i][n]==1)

f[i][n]=l[i][n];

d[n]=n;

for(i=2;i<=n;i++)

while(e[i]<0)

{

for(i=2;i<n;i++)

if(e[i]<0)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if((a[i][j]==1)&&(-e[i]<r[i][j]))

r[j][i]=-e[i];

else

r[j][i]=r[i][j];

else

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if((a[i][j]==1)&&(d[i]<d[j]))

d[j]=d[i]+1;

else

d[j]=d[j]+1;

}

}

}