Grafos

[Guest Adore]

Problema: Representar um mapa de ruas, por um grafo não orientado e pesado em que o peso de cada arco seja a informacao sobre a

distancia entre dois cruzamentos na mesma rua, assim como o tempo medio necessario para

se percorrer essa distancia. Os arcos devem ainda ser anotados com os locais de interesse

turıstico que estejam presentes no troco da rua que esse arco representa. Pode ainda anotar

os arcos com informacao adicional sobre a rua, como por exemplo, o valor arquitectonico dos

seus edifıcios, ou se ´e uma rua de comercio.

Trabalho para uma disciplina... Urgente!

Agradeço Resposta para: darcio.manuel@gmail.com

[Rafael Barros]

caro amigo,

se forem poucas ruas você pode construir uma matriz de adjacencia para este grafo. onde os indices serão as ruas ou seja rua 0, rua 1, rua 2, etc. e os pessos cada elemento da matriz, ai você define do jeito que você quiser usando o comando struct. tipow:

struct celula
{
       int distanciaCruzamento;
       int tempoEmSegundos;
       char turistico[80];
       ....
};

espero ter ajudado.

Editado Maio 29, 2007 por Rafael Barros

[soadmetal]

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.

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