Algoritmo de Dijkstra

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

[ Hits: 81.371 ]

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

Gerador de CPF em C++

Binário para Decimal, Hexa, Char

Boletim Escolar Com Manipulação de Arquivo

Jogo da cobrinha (Snake II) refeito em C e C++

Lista simplesmente encadeada 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

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts