Algoritmo de Dijkstra
Publicado por Vanderson Lucio Rodrigues 14/12/2005 (última atualização em 03/07/2017)
[ Hits: 82.743 ]
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; }
Calculadora elementar com ponto flutuante
Comparação entre os escalonadores BFQ e MQ-Deadline (acesso a disco) no Arch e Debian
Conciliando o uso da ZRAM e SWAP em disco na sua máquina
Servidor de Backup com Ubuntu Server 24.04 LTS, RAID e Duplicati (Dell PowerEdge T420)
Visualizar câmeras IP ONVIF no Linux sem necessidade de instalar aplicativos
Converter os repositórios Debian para o novo formato com as chaves
Instalando Spotify no Debian 13
Realizar overclock no Miyoo Mini (plus ou normal)
linux mint reconhece microfone de lapela como fone de ouvido sem micro... (4)
Erro na inicialização do Debian como resolver (2)
Como desinstalar o GIMP? [RESOLVIDO] (1)