Jump to content
Fórum Script Brasil
  • 0

Codigo de Dijkstra


luizasilval
 Share

Question

Preciso de um codigo em C do caminho minimo usando o algoritmo de Dijkstra, achei um na internet, ta funcionando direitinho, so q queria mudar ele pra poder escolher meu alvo e ele falar o caminho ate ele. Porque por ex, se eu coloco 4 vertices, ele pede certo o peso das arestas q eu ligar entres os 4 e da o caminho delas, mas não me pede meu alvo, porque posso querer saber o caminho da 2 para a 4, mas tambem posso querer da 1 para a 4. alguém PFVR SABE MUDAR?

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

#define FLSH gets(l)

int destino, origem, vertices = 0;
int custo, *custos = NULL;

void dijkstra(int vertices,int origem,int destino,int *custos)
{
   int i,v, cont = 0;
   int *ant, *tmp;
   int *z;     /* vertices para os quais se conhece o caminho minimo */
   double min;
   double dist[vertices]; /* vetor com os custos dos caminhos */


   /* aloca as linhas da matriz */
   ant = calloc (vertices, sizeof(int *));
   tmp = calloc (vertices, sizeof(int *));
   if (ant == NULL) {
      printf ("** Erro: Memoria Insuficiente **");
      exit(-1);
   }

   z = calloc (vertices, sizeof(int *));
   if (z == NULL) {
      printf ("** Erro: Memoria Insuficiente **");
      exit(-1);
   }

   for (i = 0; i < vertices; i++) {
      if (custos[(origem - 1) * vertices + i] !=- 1) {
         ant = origem - 1;
         dist = custos[(origem-1)*vertices+i];
      }
      else {
         ant= -1;
         dist = HUGE_VAL;
      }
      z=0;
   }
   z[origem-1] = 1;
   dist[origem-1] = 0;

   /* Laco principal */
   do {

      /* Encontrando o vertice que deve entrar em z */
      min = HUGE_VAL;
      for (i=0;i<vertices;i++)
         if (!z)
            if (dist>=0 && dist<min) {
               min=dist;v=i;
            }

      /* Calculando as distancias dos novos vizinhos de z */
      if (min != HUGE_VAL && v != destino - 1) {
         z[v] = 1;
         for (i = 0; i < vertices; i++)
            if (!z) {
               if (custos[v*vertices+i] != -1 && dist[v] + custos[v*vertices+i] < dist) {
                     dist = dist[v] + custos[v*vertices+i];
                  ant =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("não Existe\n");
      printf("\tCusto: \t- \n");
   }
   else {
      i = destino;
      i = ant[i-1];
      while (i != -1) {
      //   printf("<-%d",i+1);
         tmp[cont] = i+1;
         cont++;
         i = ant;
      }

      for (i = cont; i > 0 ; i--) {
         printf("%d -> ", tmp[i-1]);
      }
      printf("%d", destino);

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

void limpar(void)
{
     printf("{FONTE}33[2J"); /* limpa a tela */
     printf("{FONTE}33[1H"); /* poe o curso no topo */
}

void cabecalho(void)
{
    limpar();
   printf("Implementacao do Algoritmo de Dijasktra\n");
   printf("Comandos:\n");
   printf("\t d - Adicionar um Grafo\n"
           "\t r - Procura Os Menores Caminhos no Grafo\n"
           "\t CTRL+c - Sair do programa\n");
   printf(">>> ");
}

void add(void)
{
   int i, j;

   do {
      printf("\nInforme o numero de vertices (no minimo 2 ): ");
      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 = -1;

   printf("Entre com as Arestas:\n");
   do {
      do {
         printf("Origem da aresta (entre 1 e %d ou '0' para sair): ", vertices);
         scanf("%d",&origem);
      } while (origem < 0 || origem > vertices);

      if (origem) {
         do {
            printf("Destino da aresta (entre 1 e %d, menos %d): ", vertices, origem);
            scanf("%d", &destino);
         } while (destino < 1 || destino > vertices || destino == origem);

         do {
            printf("Custo (positivo) da aresta do vertice %d para o vertice %d: ",
                  origem, destino);
            scanf("%d",&custo);
         } while (custo < 0);

         custos[(origem-1) * vertices + destino - 1] = custo;
      }

   } while (origem);
}

void procurar(void)
{
   int i, j;

   /* Azul */
   printf("{FONTE}33[36;1m");
   printf("Lista dos Menores Caminhos no Grafo Dado: \n");

   for (i = 1; i <= vertices; i++) {
      for (j = 1; j <= vertices; j++)
         dijkstra(vertices, i,j, custos);
      printf("\n");
   }

   printf("<Pressione ENTER para retornar ao menu principal>\n");
   /* Volta cor nornal */
   printf("{FONTE}33[m");
}

int main(int argc, char **argv) {
   int i, j;
   char opcao[3], l[50];

   do {

       cabecalho();
      scanf("%s", &opcao);

      if ((strcmp(opcao, "d")) == 0) {
         add();
      }
      FLSH;

      if ((strcmp(opcao, "r") == 0) && (vertices > 0) ) {
         procurar();
         FLSH;
      }

   } while (opcao != "x");

   printf("\nAte a proxima...\n\n");

   return 0;
}

562a77b63fecc_Sem_ttulo1.thumb.png.5cdb5562a77c1d6479_Sem_ttulo2.thumb.png.a7f77

Creditos ao dono do codigo acima q n sei quem é.

Link to comment
Share on other sites

0 answers to this question

Recommended Posts

There have been no answers to this question yet

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share



  • Forum Statistics

    • Total Topics
      149.9k
    • Total Posts
      646.8k
×
×
  • Create New...