Algoritmo de Dijkstra

Publicado por Vanderson Lucio Rodrigues 14/12/2005 (última atualização em 03/07/2017)

[ Hits: 65.659 ]

Homepage: http://www.vandersongold.com.br

Download dijkstra.c

Download nova_versao_dijkstra.cpp (versão 2)




"O Algoritmo de Dijkstra (E.W. Dijkstra) é um dos algoritmos que calcula o caminho de custo mínimo entre vértices de um grafo."
Bem simples e muito útil. confira. ;)
[]'s

  



Versões atualizadas deste script

Versão 2 - Enviado por Vinícius Lopes de Melo em 20/06/2017

Changelog: Após algumas correções ( (int *)calloc e ausência da biblioteca strings.h) a versão atual está rodando na versão 16.01 do Code::Blocks. Bons estudos!

Download nova_versao_dijkstra.cpp


Esconder código-fonte

/*   
* Este programa implementa o algoritmo de Dijasktra para o problema do 
* caminho de custo minimo em grafos dirigidos com custos positivos nas
* arestas.
*
* @autor : vanderson lucio
* @e-mail: vanderson.gold@gmail.com
*
*/

#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[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;

   /* Laco principal */
   do {

      /* Encontrando o vertice que deve entrar em z */
      min = HUGE_VAL;
      for (i=0;i<vertices;i++)
         if (!z[i])
            if (dist[i]>=0 && dist[i]<min) {
               min=dist[i];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[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);

   /* 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];
      while (i != -1) {
      //   printf("<-%d",i+1);
         tmp[cont] = i+1;
         cont++;
         i = ant[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 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[i] = -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;
}

Scripts recomendados

[C] Raiz quadrada

Distribuição Eletronica de Elementos Químicos em C++

Jogo para adivinhar o numero

Agenda Eletrônica

Vírus didático para Linux em C


  

Comentários
[1] Comentário enviado por piazinhodolinux em 16/12/2005 - 15:45h

ai irmão, esse código é pra linux certo?!
no win naum roda...
Valeu!

[2] Comentário enviado por poet em 16/12/2005 - 18:55h

Ola ,
Não testei no windows, mas se seu complidor é padrão ansi, deveria rodar
qual é a mensagem de erro que ocorre ?

[]´s

[3] Comentário enviado por poet em 16/12/2005 - 18:55h

Opa desculpa...

Na verdade nao vai funcionar pelo seguinte: Estou usando um recurso dos terminais linux na funcao:
void limpar(void)
{
printf("{FONTE}33[2J"); /* limpa a tela */
printf("{FONTE}33[1H"); /* poe o curso no topo */
}

Portanto se voce retirar essa funcao do programa deve funcionar.

Qualquer duvida, estarei aqui.

[4] Comentário enviado por ramonufmg em 04/11/2006 - 11:14h

Excelente!
Cara muito bom o seu código, compilei-o no RWindows e funcionou perfeitamente, com excessão dos comandos citados acima. Estou fazendo um trabalho comparativa sobre métodos de roteirização urbana e me ajudou muito já ter algo implementado.
Obrigado.

[5] Comentário enviado por c.rafael em 12/09/2007 - 20:41h

Carinha,

Para mim está dando erro aqui: "ant = calloc (vertices, sizeof(int *));"

Erro:
invalid conversion from 'void*' to 'int*'

O que pode ser?

[6] Comentário enviado por poet em 08/05/2008 - 08:06h

seu compilador deve ser c++, por isso precia fazer um cast explicito:

para resolver, ponha "(int*)", antes da chamda de calloc, por exemplo:

ant = calloc (int*) (vertices, sizeof(int *));"


[]''s

[7] Comentário enviado por rafael56 em 01/10/2009 - 23:57h

Opa...muito bom o código, me ajudo a entender bem com a lógica do dijkstra...vai me quebra um galho no trabalho do semestre...

[8] Comentário enviado por robsonbraga em 30/11/2009 - 10:07h

Cara to tentando compilar no Dev C++ e me da o seguinte erro:
expected primary-expression before "int"

isso ja feita a alteração recomendada pra c++

Alguma dica?

[9] Comentário enviado por pollyannadias em 11/05/2010 - 13:42h

Por acaso vc não tem uma implementação do algoritmo de Prim em C?
Grata

[10] Comentário enviado por jemessonlima em 20/05/2010 - 19:03h

Ta tudo certo galera mesmo a única coisa é fazer um casting tipo: (int *)
custos = (int *) malloc(sizeof(int)*vertices*vertices);

[11] Comentário enviado por relue em 28/09/2011 - 22:05h

codigo nao funciona pelo gcc do linux, segue o erro:

dijkstra.c: In function ‘main’:
dijkstra.c:185: warning: format ‘%s’ expects type ‘char *’, but argument 2 has type ‘char (*)[3]’
/tmp/ccMEM5bH.o: In function `main':
dijkstra.c:(.text+0x7d4): warning: the `gets' function is dangerous and should not be used.

se o que significa isso?

[12] Comentário enviado por panicogyn1990 em 11/11/2011 - 09:19h

tente compilar no terminal do windows

gcc dijkstra.c -o teste

executar:

teste

[13] Comentário enviado por Beorlegui em 01/05/2013 - 20:01h

Tentei compilar no Dev C++ e dá o esse erro:
expected primary-expression before "int"

Eu já fiz a alteração para c++.
Alguém poderia me ajudar?

[14] Comentário enviado por sassadabahia em 20/06/2014 - 17:44h

Caro amigo o meu é windows e dev c++, porem existe um erro no if ((strcmp(opcao, "d")) == 0) { e if ((strcmp(opcao, "r") == 0) && (vertices > 0) )
pode ajudar-me?

[15] Comentário enviado por sassadabahia em 20/06/2014 - 17:54h

vc tem email para contato, gostaria de negociar um programa.

[16] Comentário enviado por luizasilval em 23/10/2015 - 14:46h

como eu faria para ele me dizer qual o caminho minimo? pq ele mostra o peso de cada vertice com as setinhas e tudo, mas nao diz tipo "o caminha minimo é"


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts