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

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, pastrez distanta pana la nod.
== code(c) |
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;
		}
	}
}
==