h1. Flux maxim intr-o retea de transport, algoritmul lui Dinic
h1. Algoritmul lui Dinic
(Categoria _Grafuri_, autor(i) _Alexandru Mosoi_)
TODO:
* ancore la pasi
* poze si exemplificare
* analiza complexitatii
h2. Introducere
Acest articol presupune o familiarizare anterioara cu grafuri si retele de transport. Pentru a elimina neclaritati vom da urmatoarea definitie: _O **retea de transport** este un graf orientat in care avem un nod **sursa**, un nod **destinatie**, iar fiecarei muchii ii este asociata o capacitate superioara_. Problema este clasica: cat flux putem baga de la sursa la destinatie fara a depasi capacitatea fiecarei muchii. Algoritmul pe care probabil deja il cunoasteti poarta numele "Edmonds-Karp":http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm si are complexitatea O(N*M*M). Algoritmul **Dinic**, prezentat in acest articol, are complexitatea O(N*N*M). Am folosit notatiile obisnuite: N - numarul de noduri, M - numarul de muchii.
Acest articol presupune o familiarizare anterioara cu grafuri si retele de transport. Pentru a elimina neclaritati vom da urmatoarea definitie: _O **retea de transport** este un graf orientat in care avem un nod **sursa**, un nod **destinatie**, iar fiecarei muchii ii este asociata o capacitate superioara_. Problema este clasica: cat flux putem baga de la sursa la destinatie fara a depasi capacitatea fiecarei muchii. Algoritmul pe care probabil deja il cunoasteti poarta numele "Edmonds-Karp":http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm si are complexitatea O(N*M*M). Algoritmul **Dinic**, prezentat in acest articol, are complexitatea O(N*N*M). Am folosit notatiile obisnuite: $N$ - numarul de noduri, $M$ - numarul de muchii.
h2. Exemplu
Pentru o mai buna intelegere a articolului vom lucra cu urmatorul exemplu (imagine preluata de pe "Wikipedia"http://en.wikipedia.org"):
(aici vine o imagine).
Pentru o mai buna intelegere a articolului vom lucra cu urmatorul exemplu (imagine preluata de pe "Wikipedia":http://en.wikipedia.org):
!dinic?Dinic_flow_example_1.png!
h2. Descriere
Algoritmul Edmonds-Karp presupune gasirea unui drum de crestere in reteaua reziduala si marirea fluxului total pana cand nu mai exista un drum de crestere. O observatie importanta este ca la fiecare pas in reteua reziduala exista mai multe drumuri de crestere de lungime minima.
h3. Pasul 1
Algoritmul Edmonds-Karp presupune gasirea, cat timp exista, a unui drum de crestere in reteaua reziduala si marirea fluxului total. Evident, la fiecare pas pot exista mai multe drumuri de crestere (care au luO observatie importanta este ca la fiecare pas in reteua reziduala exista mai multe drumuri de crestere de lungime minima.
Primul pas este sa construim din reteua reziduala un graf orientat aciclic in care sa regasim toate drumurile de lungime minima de la sursa la destinatie. Evident in acest dag toate muchiile vor avea capacitatea cel putin 1. Cum construim acest graf? Destul de simplu. Modificam putin bfs-ul de la Edmonds-Karp precum urmeaza. Pentru fiecare nod, calculam distanta (ca numar de muchii) de la sursa pana la el. O muchie (u, v) cu capacitatea c > 0 in reteaua reziduala este adaugata la graful construit doar daca distanta de la sursa la u plus 1 este egala cu distanta de la sursa la nodul u (pe scurt, daca muchia (u, v) apartine unui drum de crestere).
Primul pas este sa construim din reteua reziduala un graf orientat aciclic in care sa regasim toate drumurile de lungime minima de la sursa la destinatie. Evident in acest dag toate muchiile vor avea capacitatea cel putin 1. Cum construim acest graf? Destul de simplu. Modificam putin bfs-ul de la Edmonds-Karp precum urmeaza. Pentru fiecare nod, calculam distanta (ca numar de muchii) de la sursa pana la el. O muchie $(u, v)$ cu capacitatea $c > 0$ in reteaua reziduala este adaugata la graful construit doar daca distanta de la sursa la $u$ _plus_ $1$ este egala cu distanta de la sursa la nodul $v$ (pe scurt, daca muchia $(u, v)$ apartine unui drum de lungime minima de la sursa la destinatie).
Aici aveti un exemplu de cod pentru a construi graful. In codul de mai jos construiesc noul graf odata cu parcurgerea breadth first. _flow_ reprezinta matricea de adiacenta pentru reteaua reziduala, iar _edges_ memoreaza pentru fiecare nod lista de vecini in graful construit.
In exemplul de mai jos noul graf este construit odata cu parcurgerea in latime. _flow_ reprezinta matricea de adiacenta pentru reteaua reziduala, iar _edges_ memoreaza pentru fiecare nod lista de vecini in graful construit (atentie: muchiile inverse nu apar).
== code(c) |
while (!que.empty()) {
}
==
Scriind acest articol, mi-am dat seama ca se putea un pic mai simplu, fara sa tin cont de distanta.
Nota: Scriind acest articol, mi-am dat seama ca se putea un pic mai simplu, fara sa tin cont de distanta. Cand se expandeaza nodul _u_, muchia _(u, v)_ se adauga la graf doar daca _v_ este nevizitat. Un nod este **vizitat** daca a fost expandat (scos din coada).
h3. Pasul 2
Urmatorul pas este sa bagam flux in graful creat (subraf a retelei reziduale). Acesta operatie se poate face usor cautand drumuri de crestere si pompand flux pe aceste drumuri pana cand nu mai gasim nici un drum. Dupa ce s-a gasit un drum *NU* se face o reactualizare a formei grafului creat la pasul 1, ci doar asupra capacitatilor muchiilor.
Observatie: daca am gasit un drum de la sursa la destinatie atunci fluxul maxim pe care il pot pompa prin acest drum de crestere este maximul dintre capacitatile muchiilor de pe drum.
O imbunatatire semnificativa este sa se tina cont ca unele drumuri au un inceput comun. Sa presupunem drumurile $sursa -> ...(drum)... -> nod -> ...(drum 1)... -> destinatie$ si $sursa -> ...(drum)... -> nod -> ...(drum 2)... -> destinatie$. Cele doua drumuri au in comun portiunea $sursa -> ...(drum)... -> nod$. Sa cautam drumurile cu un DFS recursiv. Daca drumurile sunt cautate cu un DFS recursiv, atunci dupa ce se ajunge in $nod$ cu posibilitatea de a pompa maxim $C$ flux, si dupa ce introduc $B$ flux pe primul drum, pe al doilea drum mai pot baga cel mult $C-B$ flux.
== code(c) |
int do_df(int node, int cap) {
if (cap == 0)
return 0;
if (node == D)
return cap;
int bag = 0;
for (int i = 1; i <= edges[node][0]; ++i) {
const int next = edges[node][i];
if (flow[node][next] == 0)
continue;
const int r = do_df(next, min(cap-bag, flow[node][next]));
if (r) {
flow[node][next] -= r;
flow[next][node] += r;
bag += r;
}
}
return bag;
}
==
Functia do_df() pompeaza fluxul maxim in graful construit la **pasul 1**. Datorita formei particulare a grafului si ca forma sa nu se schimba dupa fiecare drum de crestere algoritmul nu are deficienta intalnita la algoritmul Ford-Fulkerson.
h3. Pasul 3
Cat timp mai exista drum de crestere (sau fluxul introdus la pasul anterior este strict pozitiv) reiau algoritmul de la **Pasul 1**.
h2. Comentarii
==user(user="vlad_popa" type="tiny")== : Nu stiu de voi, dar mie mi se pare algoritmul foarte folositor, mai ales in cazuri in care trebuie sa implementezi un algoritm de flux in care ai limite destul de mari... Bravo Alex and... Keep up the good work!
