Algoritmul Ford Fulkerson

Aspecte teoretice:

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-Fulkerson este Θ(F • (M + N)). Se observă că, în cazul în care valoarea fluxului este foarte mare, acest ordin de complexitate este inacceptabil.

Implementare:

Cod Sursa C++

// FordFulkersonCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <string.h>
#include <iostream>
#include <stdio.h> 
#include <conio.h>
 
using namespace std;
 
//nodul de intrare este nodul 1, nodul de iesire este nodul n 
struct edge
{
	int x;
	int y;
	int capacitate;
	int flux;
}muchie[20];
int i, j, n, m, fluxmax = 0, a[20][20], gn[20][20], c[20], drum[20], dimdr;
char eticheta[20];
 
void citire_date()
{
	int x, y, cap; 
	cout << "nr de noduri= "; cin >> n;
	cout << "nr de muchii= "; cin >> m;
	for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
		a[i][j] = 0;
	for (i = 1; i <= m; i++)
	{
		cout << "nodul sursa= "; cin >> x;
		cout << "nodul destinatie= "; cin >> y;
		cout << "capacitate= "; cin >> cap;
		a[x][y] = 1;
		muchie[i].x = x;
		muchie[i].y = y;
		muchie[i].capacitate = cap;
		muchie[i].flux = 0;
	}
}
 
void afisare_matrice(int mat[20][20])
{
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
			cout << mat[i][j];
		cout << endl;
	}
}
 
void construct_matr()
{  //se constr gn, matricea grafului neor asoc retelei 
	for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
		gn[i][j] = 0;
	for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
	if (a[i][j] == 1)
	{
		gn[i][j] = 1;
		gn[j][i] = 1;
	}
}
 
int calcul_delta(int vec[20], int dim)
{  //se calc flux minim pe lant 
	int min = 30000;
	for (i = 1; i <= m; i++)
	for (j = 2; j <= dim; j++)
	if ((muchie[i].x == vec[j - 1]) && (muchie[i].y == vec[j]))    //daca x-ul din muchie corespunde cu cel din lantul generat      
	if (a[vec[j - 1]][vec[j]] == 1)
	if (muchie[i].capacitate - muchie[i].flux<min)
		min = muchie[i].capacitate - muchie[i].flux;
	else if (a[vec[j]][vec[j - 1]] == 1)
	if (muchie[i].flux<min)
		min = muchie[i].flux;
	return min;
}
 
int saturat(int vec[20], int dim)
{
	int ok = 0;
	for (j = 2; j <= dim; j++) //varfuri    
	for (i = 1; i <= m; i++)  //muchii      
	if ((muchie[i].x == vec[j - 1]) && (muchie[i].y == vec[j]))
	if (muchie[i].flux == muchie[i].capacitate)
		ok = 1;
	return ok;
}
 
void resetare()
{
	for (i = 1; i <= n; i++)
		eticheta[i] = '0';
	eticheta[1] = '+';
}
 
void eticheteaza(int vec[20], int dim)
{
	int delta;
	//if(saturat(vec,dim)==0) 
	if ((eticheta[n] != '+') || (eticheta[n] != '-'))
	{
		resetare();
		delta = calcul_delta(vec, dim);
		fluxmax = fluxmax + delta;
		for (j = 2; j <= dim; j++) //varfuri    
		for (i = 1; i <= m; i++)  //muchii       
		if ((muchie[i].x == vec[j - 1]) && (muchie[i].y == vec[j]))
		if (a[vec[j - 1]][vec[j]] == 1)
		{
			muchie[i].flux = muchie[i].flux + delta;
			if (vec[j - 1] == 1)
				eticheta[vec[i]] = '+';
			eticheta[vec[j]] = '+';
		}
		else
		{
			muchie[i].flux = muchie[i].flux - delta;
			eticheta[vec[j]] = '-';
		}
	}
	if ((eticheta[n] != '+') && (eticheta[n] != '-'))
		//if(saturat(vec,dim)==0)       
		eticheteaza(vec, dim);
}
 
void verifica_lant(int vec[20], int dim)
{
	int ok = 1;
	for (i = 2; i <= dim; i++)
	if (gn[vec[i - 1]][vec[i]] == 0)
		ok = 0;
	if (ok == 1)
		eticheteaza(vec, dim);
}
 
void tipar(int k)
{
	int ok = 0, aux[20], dimaux = 0; k++;
	for (i = 1; c[1] == 1 && c[i - 1] != n; i++)
	{
		dimaux++;
		aux[dimaux] = c[i];
	} //se verifica daca lantul generat acum e diferit de cel generat anterior 
	//if(dimdr!=dimaux)   
	for (i = 1; i <= dimaux; i++)
	if (drum[i] != aux[i])
		ok = 1;
	if (ok == 1)
	{
		dimdr = dimaux;
		for (i = 1; i <= dimdr; i++)
			drum[i] = aux[i];
		verifica_lant(drum, dimdr);
	}
}
 
int valid(int k)
{
	int i, ok = 1;
	for (i = 1; i <= k - 1; i++)
	if (c[i] == c[k])
		ok = 0;
	return ok;
}
 
void bktr(int k)
{
	int i;
	for (i = 1; i <= n; i++)
	{
		c[k] = i;
		if (valid(k) == 1)
		if (k == n) tipar(k);
		else bktr(k + 1);
	}
}
 
void main()
{
	citire_date();
	construct_matr();
	bktr(1);
	printf("\nFlux maxim=%d\n", fluxmax);
	system("Pause");
}

Rezultat: