Dúvida sobre como implemementar o algoritmo de dijkstra na linguagem C

joaovitor11
(usa Outra)

Enviado em 05/03/2017 - 15:32h

Criei a função

void dijkstra(double **matrix, int origem, int destino, int linhas, int colunas); 

para obter o menor caminho como também o menor custo, mas não obtive sucesso.

Agradeço desde já quem possa me ajudar, pois já tentei de tudo.

#include <stdio.h>

#include <stdlib.h>

#include <math.h>



void dijkstra(double **matrix, int origem, int destino, int linhas, int colunas);

void inicializa1(double **m, double v, int linha, int coluna);

void conecta1(double **m, int a, int b, double v);

void exibe_caminho1(double **m, int a, int b);

double** alocarMatriz(int Linhas, int Colunas);

void imprime_mat1(double **m, int linhas, int colunas);



int main(){

int g[tam][tam], g1[tam][tam], c[tam][tam], p[tam][tam], cd[tam][tam], a, b, resp, x, linhas=2, colunas, linha, coluna;

double **mat;

system("cls");



do{

    printf("Digite o numero de colunas: ");

    scanf("%d", &colunas);

} while (colunas < 1);



mat = alocarMatriz(linhas, colunas);

inicializa1(mat, 0,linhas,colunas); 



do{

    do{

        printf("Digite o numero da linha: ");

        scanf("%d", &linha);

    } while (linha >= linhas);



    do{

        printf("Digite o numero da coluna: ");

        scanf("%d", &coluna);

    } while (coluna >= colunas);



    if (linha != -1 && coluna != -1){

        if (linha == coluna){

            conecta1(mat, linha, coluna, sqrt(2.0));

        }

        else{

            conecta1(mat, linha, coluna, 1.0);

        }

    }



    imprime_mat1(mat, linhas, colunas);

} while (linha != -1 && coluna != -1);

do

{

    printf("Digite o vertice de origem: ");

    scanf("%d", &a);

    if ((a < 0) || (a>linhas))

        printf("\n\nVERTICE INVALIDO! DIGITE NOVAMENTE!\n\n");

}while ((a < 0) || (a > linhas));



do

{

    printf("Digite o vertice de destino: ");

    scanf("%d", &b);

    if (b < 0 || a > colunas)

        printf("\n\nVERTICE INVALIDO! DIGITE NOVAMENTE!\n\n");

}while ((colunas < 0) || (coluna> colunas));



printf("%d => ", a);

dijkstra(mat, a, b,linhas,colunas);

printf("%d", b);

system("PAUSE");

return 0;

}



void dijkstra(double **matrix, int origem, int destino, int linhas, int colunas){

int i,v, cont = 0,j;

double **ant, **tmp;  

double **z;     /* vertices para os quais se conhece o caminho minimo */

double min;

double **dist = (double **) malloc(linhas * sizeof(double*)); /* vetor com os custos dos caminhos */



/* aloca as linhas da matriz */

ant = (double **) malloc (linhas * sizeof(double *));

tmp =  (double **) malloc (linhas * sizeof(double *));

if (ant == NULL) {

   printf ("** Erro: Memoria Insuficiente **");

   exit(-1);

}



z = (double **) malloc (linhas * sizeof(double *));

if (z == NULL) {

   printf ("** Erro: Memoria Insuficiente **");

   exit(-1);

}



for (i = 0; i < linhas; i++){ 

    ant[i] = (double*)malloc(colunas * sizeof(double));

    tmp[i] = (double*)malloc(colunas * sizeof(double)); 

    z[i] = (double*)malloc(colunas * sizeof(double)); 

    dist[i] = (double*)malloc(colunas * sizeof(double)); 

 }   



for (i = 0; i < linhas; i++) {

    for(j=0;j<colunas; j++){

       if (matrix[(origem - 1) * linhas + i][(origem - 1) * colunas + i] !=-            {

     ant[i][j] = origem - 1;

     dist[i][j] = matrix[(origem-1)*linhas+i][(origem-1)*colunas+j];

  }

  else {

     ant[i][j]= -1;

     dist[i][j] = HUGE_VAL;

  }

  z[i][j]=0;

}

}

z[origem-1][destino-1] = 1.0;

dist[origem-1][destino-1] = 0.0;



/* Laco principal */

do {



  /* Encontrando o vertice que deve entrar em z */

  min = HUGE_VAL;

  for (i=0;i<linhas;i++){

      for(j=0;j<colunas;j++){

     if (!z[i][j])

        if (dist[i][j]>=0 && dist[i][j]<min) {

           min=dist[i][j];v=i;

        }

      }

  }



  /* Calculando as distancias dos novos vizinhos de z */

  if (min != HUGE_VAL && v != destino - 1) {

     z[v][v] = 1;

     for (i = 0; i < linhas; i++){

         for(j=0; j<colunas; j++){

        if (!z[i]) {

           if ((matrix[v*linhas+i][v*colunas+j] != -1) && (dist[v][v] + matrix[v*linhas+i][v*colunas+j] < dist[i][j])) {

                 dist[i][j] = dist[v][v] + matrix[v*linhas+i][v*colunas+j];

              ant[i][j] =v;

              }

          }

        }

     }

  }

} while (v != destino - 1 && min != HUGE_VAL);



/* Mostra o 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][i-1];

   while (i != -1) {

   //   printf("<-%d",i+1);

     tmp[cont][cont] = i+1;

     cont++;

     i = ant[i][i];

  }



  for (i = cont; i > 0 ; i--) {

     printf("%d -> ", tmp[i-1]);

  }

  printf("%d", destino);



  printf("\n\tCusto:  %d\n",(int) dist[destino-1]);

}

}



void exibe_caminho1(double **m, int a, int b){

double k, d, r;

k = ((m[a][b]));

if (k != 0)

{

    exibe_caminho1(m, a, k);

    printf("%d => ", k);

    exibe_caminho1(m, k, b);

}

}



double** alocarMatriz(int Linhas, int Colunas){ 



int i, j; 

double **m = (double**)malloc(Linhas * sizeof(double*)); 



for (i = 0; i < Linhas; i++){ 

    m[i] = (double*)malloc(Colunas * sizeof(double)); 

    for (j = 0; j < Colunas; j++){ 

        m[i][j] = 0; 

    }

}

return m; 

}



void inicializa1(double **m, double v, int linha, int coluna){

int i, j;

i = j = 0;

while (i != linha)

{

    while (j != coluna)

    {

        m[i][j] = v;

        j++;

    }

    j = 0;

    i++;

}

}



void conecta1(double **m, int a, int b, double v){

     m[a][b] = v;

}



void imprime_mat1(double **m, int linhas, int colunas){

     int i, j, k;

     for (i = 0; i < linhas; i++){

          for (j = 0; j < colunas; j++){

               printf("%.1f   ", m[i][j]);

     }

     printf("\n");



}

system("PAUSE");

}