Olá pessoal!!!
Sou novo na lista e tb na programação java.
Programa na em C++, e além do mais não orientado!!!
Fiz um pequeno programa pra calcular o menor caminho entre dois vértice
de um grafo.
Se alguém puder de dar um dica de como fazê-lo em java, ficarei muito
agradecido!
Obrigado!!!
Elton
****************************PROGRAMA******************************************
//Em 23/04/2001
#include<iostream.h>
#include<conio.h>
#define TAM 30
#define pinfinito 3.4e34
struct vertex{ int ant,
saiu;
float peso;};
void inicializamat(float[TAM][TAM],int);
void inicializavet(vertex[TAM],int,int);
void calcula(float[TAM][TAM],vertex[TAM],int,int,int,int&);
void imprime(vertex[TAM],int i);
void main()
{
vertex vertice[TAM];
float caminho[TAM][TAM];
int resultado[TAM],
i,
vertexinicio,
vertexfim,
nvertex; //armazema a quantidade de vertice do grafo
cout<<" Informe a quantidade de vertice do grafo: ";
cin>>nvertex;
inicializamat(caminho,nvertex);
cout<<"informe o vertice inicial e o final: ";
cin>>vertexinicio>>vertexfim;
inicializavet(vertice,vertexinicio,nvertex);
calcula(caminho,vertice,nvertex,vertexinicio,vertexfim,i);
if(i != vertexfim)
cout<<"Nao exite caminho de "<<vertexinicio<<" e "<<vertexfim;
else
imprime(vertice,vertexfim);
getch();
}
void inicializamat(float caminho[TAM][TAM], int n)
{
int i,
j;
for(i = 0; i < n; i++)
{
for(j = 0; j <n; j++)
{
clrscr();
cout<<"Existe caminho entre o vertice "<<i<<" e "<<j<<":";
cin>> caminho[i][j];
}
}
}
void inicializavet(vertex v[TAM], int vinicial, int qd)
{
for(int i = 0; i < qd; i++)
{
v[i].ant = -1;
v[i].peso = -1.0;
v[i].saiu = 0;//falso
}
v[vinicial].peso = 0.0;
v[vinicial].saiu = 1;//verdadeiro
}
void calcula(float caminho[TAM][TAM], vertex vertice[TAM],int qd, int
vi,int vf int& i)
{
int i = vi, //armazena a linha corrente
menor_peso = -1;//armazena o vertice que e' atingido pelo vertice
//atual e possui menor peso
while(i != vf && vertice[i].peso != -1.0){
for(int j = 0; j < qd; j++)
{
if(caminho[i][j] != -1.0)// existe caminho
{
if(vertice[j].peso == -1.0)
{//ainda nao foi visitado
vertice[j].ant = i;
vertice[j].peso = caminho[i][j] + vertice[i].peso;
menor_peso = j;
}
else
{
if(vertice[j].peso > caminho[i][j] + vertice[i].peso)
{
vertice[j].peso = caminho[i][j] + vertice[i].peso;
vertice[j].ant = i;
menor_peso = j;
}
}
}
}
for( j = 0; j < qd; j++)
{//procurar o indice do vertice que e' atingido com menor peso
if(menor_peso == -1)
{//o vertice[i], nao tem saida para nenhum outro vertice
if(vertice[j].saiu == 0)
menor_peso = j;
}
else{
if(vertice[j].saiu == 0 && vertice[j].peso <
vertice[menor_peso].peso && vertice[j].peso != -1.0)
menor_peso = j;
}
}
if(menor_peso == -1)
{//percorre o vetor e nao encontra caminho
vertice[i].peso = -1.0; //termina
}
else{
vertice[menor_peso].saiu = 1;//verdadeiro
i = menor_peso;
menor_peso = -1;
}
}
}
void imprime(vertex vertice[TAM], int vf)
{
int pilha[30];
int topo = 0;
int corrente = vf;
while(corrente != -1)
{
pilha[topo++] = corrente;
corrente = vertice[corrente].ant;
}
while(topo != 0)
{
cout << pilha[--topo] << " ";
}
}
------------------------------ LISTA SOUJAVA ----------------------------
http://www.soujava.org.br - Sociedade de Usuários Java da Sucesu-SP
dúvidas mais comuns: http://www.soujava.org.br/faq.htm
regras da lista: http://www.soujava.org.br/regras.htm
para sair da lista: envie email para [EMAIL PROTECTED]
-------------------------------------------------------------------------
