Nesta edição da Programar, não quisemos deixar de lado uma das linguagens mais usadas de todos os tempos.
A famosa linguagem C
E nesta edição comemorativa dos 10 anos da nossa revista, achamos que faria todo o sentido recordar um algoritmo, que em algum dia das nossas vidas, todos nós, programadores ouvimos falar… o não menos famoso que a própria linguagem C, o algoritmo de Dijkstra… e porque este algoritmo? Porquê este refere, o caminho do custo mínimo. E todos nós sabemos que a nossa revista já percorreu muitos caminhos até chegamos à edição 53.
Ora para os mais distraídos, e para os menos recordados, este algoritmo data do ano de 1956, tendo tido a sua primeira publicação em 1959. Foi criado por um matemático computacional holandês, Edsger Dijkstra. E trouxe uma solução que vários procuravam na altura, a solução para o problema do caminho mais curto num grafo dirigido.
Este algoritmo é muito útil para minimizar custos em várias áreas como por exemplo, na implementação de redes (por exemplos redes OSPF), ou no conhecido sistema GPS.
Em termos teóricos, o algoritmo é simples… Ora vejamos…
Num dado vértice (nó) no grafo, o algoritmo localiza o caminho com a menor custo (isto é, o caminho mais curto) entre esse vértice e todos os outros vértices, recorrendo ao peso/custo da aresta. Este sistema, pode também ser usado para encontrar custos de caminhos mais curtos a partir de um único vértice para um vértice de destino parando o algoritmo uma vez que o caminho mais curto para o vértice destino tiver sido determinado.
Voltando ao exemplo do GPS, se os vértices do grafo representarem cidades e os custos de caminho representarem distâncias entre as cidades ligadas por uma estrada directa, o algoritmo de Dijkstra pode ser usado para encontrar o caminho mais curto entre uma cidade e todas as outras cidades.
A nível de algoritmo temos o seguinte:
Seja G(V,A) um grafo orientado e s um vértice de G:
- Atribuir valor zero à estimativa do custo mínimo do vértice s (a raiz da busca) e infinito às restantes estimativas;
- Atribuir um valor qualquer aos precedentes (o precedente de um vértice t é o vértice que precede t no caminho de custo mínimo de s para t);
- Enquanto houver vértice aberto:
- Seja k um vértice ainda aberto cuja estimativa seja a menor dentre todos os vértices abertos;
- Feche o vértice k;
- Para todo vértice j ainda aberto que seja sucessor de k faça:
- Some a estimativa do vértice k com o custo do arco que une k a j;
- Caso esta soma seja melhor que a estimativa anterior para o vértice j, substituir e anotar k como precedente de j.
Passemos agora à parte da implementação em C.
#include <stdio.h> #include <stdlib.h> #include <math.h> #define FLSH gets(l) /* definir variavies */ 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; /* Ciclo principal */ do { /* Encontra 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; } /* Calcula 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 procura */ 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 cabecalho(void) { printf("Implementacao do Algoritmo de Dijasktra\n"); printf("Comandos:\n"); printf("\t d - Adicionar Grafo\n" "\t r - Procura Os Menores Caminhos no Grafo\n" "\t CTRL+C para Sair do programa\n"); printf("-------- "); } void add(void) { int i, j; do { printf("\nQual o numero de vertices (numero 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("Insira 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("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("ENTER para voltar ao menu inicial>\n"); /* Volta cor normal */ printf("\033[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("\nOver & Out\n\n"); return 0; }
Quero recordar ao leitor que esta é apenas uma das várias maneiras e formas de implementar este algoritmo.