soadmetal

Será que alguém pode me ajudar a simplificar esse algoritimo de Ford Fulkerson. Abs. #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.

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.

E ai Wiilian tudo bem cara, aqui eu consegui o algoritimo em C para calcular o fluxo maximo porem esta muito extenso será que teria um jeito de simplificar ele. Abs. #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.

Estou precisando muito do algoritomo de Ford Fulkerson em linguagem C para Quarta - Feira...Sera que alguém poderia me ajudar ?

Estou precisando muito do algoritomo de Ford Fulkerson em linguagem C para Quarta - Feira...Sera que alguém poderia me ajudar ?

Pessoal estou muito do algoritomo de Ford Fulkerson em linguagem C para Quarta - Feira...Sera que alguém poderia me ajudar ? Desde já agradeço pessoal.