Algoritmo de Dijkstra

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:

  1. Atribuir valor zero à estimativa do custo mínimo do vértice s (a raiz da busca) e infinito às restantes estimativas;
  2. 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);
  3. 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.