/*
Jorge Luiz Taioque
jorge@lpnet.com.br
*/
 
#include
#include
#include

int destino, origem, vertices = 0;
int custo, *custos = NULL;
 
void calcula(int vertices,int origem,int destino,int *custos)
{
int i,v, contar = 0;
int *ant, *tmp;
int *z;
double min;
double dist[vertices];
 
/* criando matriz */
ant = calloc (vertices, sizeof(int *));
tmp = calloc (vertices, sizeof(int *));
if (ant == NULL) {
printf ("Memoria Insuficiente\n");
exit(-1);
}
 
z = calloc (vertices, sizeof(int *));
if (z == NULL) {
printf ("Memoria Insuficiente\n");
exit(-1);
}
 
for (i = 0; i < vertices; i++) {
if (custos[(origem - 1) * vertices + i] !=- 1) {
ant[i] = origem - 1;
dist[i] = custos[(origem-1)*vertices+i];
}
else {
ant[i]= -1;
dist[i] = HUGE_VAL;
}
z[i]=0;
}
z[origem-1] = 1;
dist[origem-1] = 0;
 
do {
 
min = HUGE_VAL;
for (i=0;i<vertices;i++)
if (!z[i])
if (dist[i]>=0 && dist[i]<min) {
min=dist[i];v=i;
}
 
if (min != HUGE_VAL && v != destino - 1) {
z[v] = 1;
for (i = 0; i < vertices; i++)
if (!z[i]) {
if (custos[v*vertices+i] != -1 && dist[v] + custos[v*vertices+i] < dist[i]) {
dist[i] = dist[v] + custos[v*vertices+i];
ant[i] =v;
}
}
}
} while (v != destino - 1 && min != HUGE_VAL);
 
/*resultado da busca*/
printf("\tDe %d para %d: \t", origem, destino);
if (min == HUGE_VAL) {
printf("Nao Existe\n");
printf("\tCusto: \t- \n");
}
else {
i = destino;
i = ant[i-1];
while (i != -1) {
tmp[contar] = i+1;
contar++;
i = ant[i];
}
 
for (i = contar; i > 0 ; i--) {
printf("%d -> ", tmp[i-1]);
}
printf("%d", destino);
 
printf("\n\tCusto: %d\n",(int) dist[destino-1]);
}
}
 
void limpar_tela(void)
{
system("clear");
}
 
void menu(void)
{
limpar_tela();
printf("Implementacao do Algoritmo de Dijasktra\n");
printf("Indice de comandos:\n");
printf("\t a - Adicionar um Grafo\n"
"\t g - Gera Caminhos\n"
"\t CTRL+c - Sair\n");
printf(">>>");
}
 
void procurar(void)
{
int i, j;
 
printf("Caminhos mais curto: \n");
 
for (i = 1; i <= vertices; i++) {
for (j = 1; j <= vertices; j++)
calcula(vertices, i,j, custos);
printf("\n");
}
 
printf("\n");
}
 
void adiciona_coordenadas(void)
{
int i, j;
 
do {
printf("\nNumero de vertices (minimo 2 ): \n");
printf(">>>");
scanf("%d",&vertices);
} while (vertices < 2 );
 
if (!custos)
free(custos);
custos = (int *) malloc(sizeof(int)*vertices*vertices);
for (i = 0; i <= vertices * vertices; i++)
custos[i] = -1;
 
printf("Quantidade de Arestas:\n");
do {
do {
printf("Origem da aresta (entre 1 e %d ou '0' para sair): \n", vertices);
printf(">>>");
scanf("%d",&origem);
} while (origem < 0 || origem > vertices);
 
if (origem) {
do {
printf("Destino da aresta (entre 1 e %d, menos %d): \n", vertices, origem);
printf(">>>");
scanf("%d", &destino);
} while (destino < 1 || destino > vertices || destino == origem);
 
do {
printf("Custo da aresta %d para o vertice %d: \n",
origem, destino);
printf(">>>");
scanf("%d",&custo);
} while (custo < 0);
 
custos[(origem-1) * vertices + destino - 1] = custo;
}
 
} while (origem);
}
 
int main(int argc, char **argv) {
int i, j;
char opcao[3], l[50];
 
do {
 
menu();
scanf("%s", &opcao);
 
if ((strcmp(opcao, "a")) == 0) {
adiciona_coordenadas();
}
 
if ((strcmp(opcao, "g") == 0) && (vertices > 0) ) {
procurar();
}
 
} while (opcao != "x");
 
printf("\n\n");
 
return 0;
}