Algoritmo de Dijkstra
Publicado por Vanderson Lucio Rodrigues 14/12/2005 (última atualização em 03/07/2017)
[ Hits: 82.613 ]
Homepage: http://www.vandersongold.com.br
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ã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
/* * 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; }
Aprenda a Gerenciar Permissões de Arquivos no Linux
Como transformar um áudio em vídeo com efeito de forma de onda (wave form)
Como aprovar Pull Requests em seu repositório Github via linha de comando
Visualizar arquivos em formato markdown (ex.: README.md) pelo terminal
Dando - teoricamente - um gás no Gnome-Shell do Arch Linux
Como instalar o Google Cloud CLI no Ubuntu/Debian
Mantenha seu Sistema Leve e Rápido com a Limpeza do APT!
Procurando vídeos de YouTube pelo terminal e assistindo via mpv (2025)
Alguém já usou o framework Avalonia para desenvolver interfaces de usu... (4)
Ajuda Pra Melhoria do NFTABLES. (8)
Sinto uma leve lentidão ao arrastar, miniminizar e restauras as janela... (2)
Pastas da raiz foram para a área de trabalho [RESOLVIDO] (7)