Anteriormente vimos que os Grafos são objetos abstratos muito interessantes e constantemente utilizados como forma de resolver problemas através de conceitos de redutibilidade.
Uma aplicação bastante comum para os grafos é a representação de mapas: As ruas são representadas por arestas, as distâncias são custos atribuídos às arestas e os locais (cidades, casas, paises, etc.) são representados pelos vértices.
Achar um caminho entre dois pontos quaisquer neste grafo é trivial: basta testar todas as possibilidades. Entretanto, esta abordagem (conhecida como método de força bruta) traz alguns incovenientes: É bastante demorada e não garante que o caminho mais curto (ou com menor custo) seja encontrado.
O grande desafio para a computação, é encontrar o caminho mais curto num espaço de tempo curto. Este problema é tradicionalmente conhecido como Problema do Caixeiro Viajante e é extremamente importante, sendo exaustivamente explorado pela computação, logística, economia, administração, biologia e várias outras áreas do conhecimento.
Na computação diversas soluções tornaram-se célebres ao longo do tempo, como o Algoritmo de Djkstra (pronuncia-se Déikstra) e o Algoritmo do Caminho Mínimo, este ultimo sendo o foco principal deste texto.
Apesar de simples, é um algoritmo eficiente, que roda em tempo quadrático (isso significa que dada uma quantidade n de vértices, um computador levará n² unidades de processamento para chegar a uma resposta).
Coloco a seguir a representação do algoritmo, uma prova matemática da sua corretude e um exemplo de implementação na linguagem de programação C.
Entrada: v0, G = V(G), A(G) onde v0, a fonte, pertence a V(G), e G é um grafo orientado, com custo real não-negativo associado a cada aresta em A(G) – custo (v,w), o custo associado à aresta (v,w), é 0 se v = w, e é infinito se (v,w) não é uma aresta.
Saída: (Dist), onde Dist(v) é a distância mínima de v0 a cada v em V(G).
1. C <– v0; Dist(v0) 0;
2. para cada v em V(G) – v0 faça {
3. Dist(v) <– custo(v0), v(); } (* fim para *)
4. enqto C <> V(G) faça {
5. (*abaixo, incrementa-se C de um elemento*)
6. “escolha w em V(G) – C tal que Dist(w) seja mínimo”;
7. Ins(w,C);
8. para cada v em vG – C faça { (* atualiza Dist *)
9. Dist(v) <– min(Dist(v), Dist(w) + custo(w, v));
10. } (* fim-para *)
11. } (* fim-enqto *)
12. resulta saída (Dist)
Corretude do algoritmo
TEOREMA O algoritmo CamMin determina corretamente os valores de Dist(v) para cada vértice v, com tempo O(n2), onde n é o número de vértices no grafo considerado.
DEMONSTRAÇÃO No algorimto acima pode-se verificar que as linhas 1-3 são executáveis em tempo O(n).
Em cada iteração das linhas 4-12, as linhas 6-8 requerem tempo O(n), e as linhas 9-11
também requerem tempo O(n). Como as linhas 4-12 são executadas n – 1 vezes, a complexidade de tempo total destas linhas é O(n2), que é a parcela dominante da complexidade de tempo de todo o algoritmo.
A certificação será provada por indução em C, e consiste de duas partes:
1. Para qualquer v em C, Dist(v) é a distância mínima de v0 a v ;
2. Para qualquer v em vG – C, Dist(v) é a distância mínima de v0 a v através de um caminho que passa só por vértices em C, exceto v ;
Para |C| – 1, o único elemento em C é v0 e é óbvio que (1) e (2) acima são válidos de acordo com as linhas 1-3 do algoritmo CamMin.
Para o passo indutivo, vamos supor que (1) e (2) acima são válidos para |C| = k – 1, isto é, vamos supor que o algoritmo CamMin é correto até antes da k-ésima iteração das linhas 4-12, para 1 < k <= n – 1. Na k-ésima iteração, w é escolhido conforme as linhas 6-8.
Vamos supor, por absurdo, que Dist(w) não é igual à distância mínima de v0 a w. Então deve existir um caminho M de v0 a w de custo menor do que Dist(w). M deve conter um outro vértice, além de w, fora de C, pois se tal vértice não existisse, w contrariaria a hipótese indutiva referente ao item (2) acima. Seja v o primeiro nestas condições. Então, a distância de v0 a v é menor do que Dist(w), pois os custos são não-negativos. Ademais, o segmento do caminho M de v0 até v está inteiramente contido em C (exceto v). Pela hipótese indutiva referente ao item (2) acima, Dist(v) é menor ou igual ao custo deste segmento de M. Conclui-se então que Dist(v) < Dist(w), mas isto contradiz a escolha de w nas linhas 6-8 (v deveria ter sido escolhido no lugar de w). Portanto, tal caminho M não deve existir e Dist(w) é o custo do caminho mínimo de v0 a w, conforme queriamos provar.
Versão em C com tempo O(n²)
Arquivos:
• Main.c: Arquivo que contém as funções para leitura e gravação de arquivos, execução do algoritmo que calcula o caminho mínimo.
Informções Técnicas:
• Computador: Intel Pentium 4
• Compilador C: Code::Blocks, gcc 4.9.9.1
• Sistema Operacional: Microsoft Windows Vista
Como utilizar o programa:
O arquivo compilado sempre busca um arquivo de texto com o nome “grafo.txt” para receber as informações sobre o grafo na forma 00 00 00, sendo que o primeiro bloco define o vértice de origem, o segundo o vértice destino e o terceiro o custo entre os dois vértices. Á partir dai a execução ocorre sem necessidade de intervenção do usuário.
O resultado final (menor distância entre v0 e os demais vértices do grafo) é impresso na tela.
O código:
/**********************************************************************
* CALCULO DA DISTANCIA MINIMA EM UM GRAFO *
* *
* MAIN.C *
* *
**********************************************************************/
/* Inclusão de Bibliotecas */
#include
#include
#include
#include
/* Valor padrão para definir vértices não adjacentes */
#define INFINITO_POSITIVO 1000
/* FUNÇÃO PRINCIPAL DO PROGRAMA */
int main()
{
/*********************************************************************/
/***************** DECLARAÇÃO DE VARIÁVEIS ************************/
/********************************************************************/
/* Variavel para trabalhar com o arquivo de texto */
FILE *txt;
/* Variaveis para trabalhar com o grafo */
int origem, destino, peso, grafo[100][100];
/* Armazena a menor distancia de v0 a todos os outros i vértices de G. */
int dist[100];
/* Vetor booleano:
1 significa que o vetor está em C. 0 significa que não está */
int C[100];
/* Variáveis auxiliares para a execução de laços no programa. */
int i,j;
/* Variável Auxiliar, para definir o vértice de V(G) analisado */
int w = 0;
/* Variavel auxiliar para definir a posição do w escolhido dentro do vetor
de distâncias. */
int posicao_w;
/* Variavel posicao_wiliar para definir |V(C)| */
int tamanho_C = 0;
/**********************************************************************/
/**************** TRABALHANDO COM O GRAFO *************************/
/*********************************************************************/
/* Atribuindo um valor infinito à todas as posições da matriz, fazendo com que
caso alguma aresta não exista, não seja utilizada pelo algoritmo de menor
caminho */
for(i = 0; i < 100; i++){
for(j = 0; j < 100; j++){
grafo[i][j] = INFINITO_POSITIVO;
}
}
/**********************************************************************/
/******************** LEITURA DE ARQUIVOS ***************************/
/*********************************************************************/
/* Abrindo o arquivo que contém o grafo */
if ( (txt = fopen(“grafo.txt”, “a+”) ) == NULL) {
/* mensagem exibida caso haja algum problema durante a abertura do arquivo */
printf(“Erro ao abrir o arquivo.”);
system(“PAUSE”);
exit(1);
}
/* Construindo o grafo em uma matrix para uso do algoritmo */
while (!feof(txt)) {
fscanf(txt,”%d”,&origem);
fscanf(txt,”%d”,&destino);
fscanf(txt,”%d”,&peso);
grafo[origem][destino] = peso; /* Atribui um peso às arestas do grafo */
}
fclose(txt);
/*********************************************************************/
/*************************** INICIO DO ALGORITMO ********************/
/*********************************************************************/
/* Começar em v0 e colocar todas as distancias num vetor de distancias */
for(i = 0; i < 100; i++){ // “Laço 1”
dist[i] = grafo[0][i];
} // Fim “Laço 1”
C[0] = 1; /* C <– v0 */
dist[0] = 0; /* Dist{v0} <– 0 */
/* Enquanto C != V(G): Enquanto houverem vértices de G fora de C, o algoritmo
será executado. Noto que o algoritmo só funciona com grafos conexos. */
while (tamanho_C < 100) { /* “Enquanto 1″ */
/* Abaixo, incrementa-se C em um elemento. */
tamanho_C += 1;
/* Define em w um custo infinito. Se houver algum vértice com custo menor
que 1000 ele será escolhido. Caso contrário, v0 é isolado e o algoritmo
é encerrado. */
w = INFINITO_POSITIVO;
/* Escolher menor das distâncias em vet_dist tal que distância n esteja em C */
for(i = 0; i < 100; i++){ /* Laço 2 */ if (C[i] == 0 & w > dist[i]) {
w = dist[i];
posicao_w = i;
} /* fim se */
} /* fim Laço 2 */
C[posicao_w] = 1; /* setando o w escolhido como vértice visitado */
/* atualizando custos em dist i a partir do w escolhido */
for(i = 0; i < 100; i++){ /* Laço 3 */ if (C[i] == 0) { if (dist[i] > (w + grafo[posicao_w][i])) dist[i] = w + grafo[posicao_w][i]; //tem que ser em V(G) – C
}
} /* Fim Laço 3 */
} /* Fim Enquanto */
/*********************************************************************/
/* *********************** Fim do algoritmo ****************************/
/*********************************************************************/
/**********************************************************************/
/***** Exibindo as menores distâncias de v0 até os demais vértices em G ******/
/*********************************************************************/
printf(” Origem Destino Distancia\n\n”);
for(i = 0; i < 100; i++){ // Laço 4 /* Como o algoritmo funciona para qualquer grafo com até 100 vértices, grafos pequenos terão muitas arestas e vértices marcados como “infinito”, ou naão existente. Para facilitar a visualização, vértices não existentes não são exibidos. */ if (dist[i] != 1000) printf(” v0 –> v%d %d \n”,i, dist[i]);
} /* Fim laço 4 */
/* Pulo de linha meramente estetético para separar mensagem de fim do
programa dos resultados (no Windows). */
printf(“\n”);
system(“pause”);
return 0;
}
0.000000
0.000000
Brainstorm de TI 
