Flux maxim intr-o retea de transport, algoritmul lui Dinic

(Categoria Grafuri, autor(i) Alexandru Mosoi)

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 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.

Exemplu

Pentru o mai buna intelegere a articolului vom lucra cu urmatorul exemplu (imagine preluata de pe "Wikipedia"http://en.wikipedia.org"):

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.

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? Pai, destul de simplu. Modificam putin bfs-ul de la Edmonds-Karp ca mai jos. Notam cu u nodul curent, cu v un nod accesibil din u in reteaua reziduala si cu c capactiatea muchiei (u, v) in reteua reziduala. Un nod este vizitat daca a fost scos in coada folosita pentru dfs.

• daca v a fost vizitat, nu facem nimic

• daca v nu a fost vizitat adaugam muchia (u, v) cu capacitatea c la graful pe care il construim.

Aici aveti un exemplu de cod pentru a construi graful. In exemplul de mai jos, din motive care acum nu-mi sunt evidente, ma folosesc distanta pana la nod (initial infinita) pentru a determina daca o muchie trebuie adaugata (sau nu) in graful care se construieste..

while (!que.empty()) {
	int node = que.front();
	que.pop();

	if (node == N-1)
		break;

	for (int i = 0; i < N; ++i) {
		if (flow[node][i] == 0)
			continue;

		if (dist[i] == -1) {
			que.push(i);
			dist[i] = dist[node]+1;
			edges[node][++edges[node][0]] = i;
		} else if (dist[i] == dist[node]+1) {
			edges[node][++edges[node][0]] = i;
		}
	}
}