Algoritimo De Ford Fulkerson

[soadmetal]

Conseguiu na net esse algoritimo de Ford Fulkerson em C, mas meu professor disse que eu tenho que simplificar ele, será que alguém pode me ajudar ?

#include <stdio.h>

#include <iostream.h>

//Definições básicas

#define BRANCO 0

#define VERDE 1

#define AZUL 2

#define MAX_NOS 1000

//Declarações

int n; // numero de nos

int e; // numero de arestas

int capacidade[MAX_NOS][MAX_NOS]; // capacidade matriz

int fluxo[MAX_NOS][MAX_NOS]; // fluxo matriz

int cor[MAX_NOS]; // array de 0 e 1

int visitado[MAX_NOS]; // armazena no array o caminho aumentado

int min (int x, int y) {

return x<y ? x : y; // returns minimum of x and y

}

//Uma fila para a busca

int origem,destino;

int f[MAX_NOS+2];

void enfilera (int x) {

f[destino] = x;

destino++;

cor[x] = VERDE;

}

int desenfilera () {

int x = f[origem];

origem++;

cor[x] = AZUL;

return x;

}

//Fila de busca no caminho aumentado

int busca (int saida, int objetivo) {

int u,v;

for (u=0; u<n; u++) {

cor = BRANCO;

}

origem = destino = 0;

enfilera(saida);

visitado[saida] = -1;

while (origem!=destino) {

u = desenfilera();

// Para todo nó adjacente a v. Se a capacidade

// de u para v na sua rede residual,

// enfilera v.

for (v=0; v<n; v++) {

if (cor[v]==BRANCO && capacidade[v]-fluxo[v]>0) {

enfilera(v);

visitado[v] = u;

}

}

}

// Se a cor do nó objetivo é azul agora,

// significa que alcançamos.

return cor[objetivo]==AZUL;

}

//Algoritimo Ford-Fulkerson

int max_fluxo (int fonte, int sorvedouro) {

int i,j,u;

// Inicializa o fluxo nulo.

int max_fluxo = 0;

for (i=0; i<n; i++) {

for (j=0; j<n; j++) {

fluxo[j] = 0;

}

}

// enquanto existir caminho expandivel,

// aumentar o fluxo ao longo desse caminho.

while (busca(fonte,sorvedouro)) {

// Determine a quantidade de nos que podemos incrementar o fluxo.

int incrementar = 999;

for (u=n-1; visitado>=0; u=visitado) {

incrementar = min(incrementar,capacidade[visitado]-

fluxo[visitado]);

}

// agora incrementar o fluxo.

for (u=n-1; visitado>=0; u=visitado) {

fluxo[visitado] += incrementar;

fluxo[visitado] -= incrementar;

}

max_fluxo += incrementar;

}

return max_fluxo;

}

//Leitura do arquivo e funcão main

void leia_arquivo() {

int a,b,c,i,j;

FILE* input = fopen("matriz.txt","r");

// leia numero de nos e arestas

fscanf(input,"%d %d",&n,&e);

// inicializa a matriz vazia

for (i=0; i<n; i++) {

for (j=0; j<n; j++) {

capacidade[j] = 0;

}

}

// leia os valores das arestas

for (i=0; i<e; i++) {

fscanf(input,"%d %d %d",&a,&b,&c);

capacidade[a] = c;

}

fclose(input);

}

int main () {

leia_arquivo();

printf("\nO fluxo maximo e: %d\n",max_fluxo(0,n-1));

printf("\n");

system ("pause");

return 0;

}

//Arquivo

/*6 10 // 6 nos, 10 edges

0 1 16 // capacidade de 0 para 1 é 16

0 2 13 // capacidade de 0 para 2 é 13

1 2 10 // capacidade de 1 para 2 é 10

2 1 4 // capacidade de 2 para 1 é 4

3 2 9 // capacidade de 3 para 2 é 9

1 3 12 // capacidade de 1 para 3 é 12

2 4 14 // capacidade de 2 para 4 é 14

4 3 7 // capacidade de 4 para 3 é 7

3 5 20 // capacidade de 3 para 5 é 20

4 5 4 // capacidade de 4 para 5 é 4*/

//Saida do progrma

//O programa verifica o fluxo máximo de 0 a 5.

[Rafael Schouery (VidaGeek)]

Procure o Algorithms in C part 5 (do Sedgewick) na sua biblioteca, ele tem uma forma muito mais simples.

A questão que o seu professor deve estar encanado é que este algoritmo usa uma busca muito sofisticada, enquanto que o método de achar fluxo máximo do Ford Fulkerson pode ser feito com uma simples busca em largura.