Floyd-Warshall [Como faço para trabalhar com pesos nas arestas]

ademario71
(usa PCLinuxOS)

Enviado em 03/07/2015 - 18:09h

//Este é o algoritmo e eu preciso concertar pra que ele trabalhe com pesos


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>

int maximo(int, int);


void warshal(int p[10][10], int n);


void warshal(int p[10][10], int n){
int i, j, k;

for(k= 1; k <= n; k++)//Percorrendo quantos caminhos por K existem
for(i= 1; i <= n; i++)//Percorrendo a matriz
for(j= 1; j <= n; j++)//percorrendo a matriz
p[i][j]= maximo(p[i][j], p[i][k] && p[k][j]);// Pegando o melhor caminho
}

int maximo(int a, int b){// pega o maior
if(a > b)
return(a);
else
return(b);
}

int main(){

int p[10][10]= {0};
int n, e, u, v, i, j;

system("cls");

printf("\n Digite a quantidade de Vertices:");//quantidade de vertices
scanf("%d", &n);

printf("\n Digite a quantidade de Arestas:");// quantidade de arestas
scanf("%d", &e);

for(i= 1; i <= e; i++){// Digita as arestas existente
printf("\n Digite os vertices que formam a aresta% d:", i);
scanf("%d%d", &u, &v);
p[u][v]= 1;
}

printf("\n Matriz de dados de entrada: \n");//Apresenta a matriz das arestas existentes
for(i= 1;i <= n; i++){
for(j= 1;j <= n; j++){
printf("%d\t", p[i][j]);
printf("\n");
}
}

warshal(p, n);
printf("\n Matriz de encerramento: \n");// Apresenta a matriz final de melhor caminho
for(i= 1; i <= n; i++){
for(j= 1; j <= n; j++){
printf("%d\t",p[i][j]);
printf("\n");
}
}

getch();
}

removido
(usa Nenhuma)

Enviado em 03/07/2015 - 18:27h

Tá, mas você viu algum erro na execução?
Outra coisa, #include <conio.h> não funciona em Linux, nem system("cls").

--
http://s.glbimg.com/po/tt/f/original/2011/10/20/a97264_w8.jpg

Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden

ademario71
(usa PCLinuxOS)

Enviado em 03/07/2015 - 18:31h

Estou rodando o programa no windows, DEV C++, é uma atividade da faculdade. Apenas quero adicionar pesos.

removido
(usa Nenhuma)

Enviado em 03/07/2015 - 18:44h

Aí é só você desenhar um grafo no papel e colocar pesos nele.
Faz o teste de mesa prá ver qual o melhor caminho.
Depois você usa um for e um scanf() prá cadastrar os pesos em tempo de execução.
E confere com o resultado do teste de mesa prá ver se o resultado do programa está certo.

EDIT:

Faça isto mais de uma vez com grafos diferentes com pesos diferentes.

--
http://s.glbimg.com/po/tt/f/original/2011/10/20/a97264_w8.jpg

Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden