Grafos- Caminho mínimo

Introdução

A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V,A), onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, grafo orientado ou digrafo. Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial.

Estruturas que podem ser representadas por grafos estão em toda parte e muitos problemas de interesse prático podem ser formulados como questões sobre certos grafos. Por exemplo, a estrutura de links da Wikipedia pode ser representada por um dígrafo: os vértices são os artigos da Wikipedia e existe uma aresta do artigo A para o artigo B se e somente se A contém um link para B. Dígrafos são também usados para representar máquinas de estado finito. O desenvolvimento de algoritmos para manipular grafos é um importante tema da ciência da computação.

Caminho mínimo

Na teoria de grafos, o problema do caminho mínimo consiste na minimização do custo de travessia de um grafo entre dois nós (ou vértices); custo este dado pela soma dos pesos de cada aresta percorrida.

Os algoritmos especializados em solucionar o problema do caminho mínimo são eventualmente chamados de algoritmos de busca de caminhos. Entre os algoritmos dessa classe, os mais conhecidos são:

•         Algoritmo de Dijkstra
•          Algoritmo de Bellman-Ford
•          Algoritmo A*
•          Algoritmo de Johnson
•          Algoritmo de Prim

Algoritmo de Dijkstra

O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 19591 2 , soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional O([m+n]log n) onde m é o número de arestas e n é o número de vértices. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford, que possui maior tempo de execução que o Dijkstra.

O algoritmo de Dijkstra assemelha-se ao BFS, mas é um algoritmo guloso, ou seja, toma a decisão que parece ótima no momento. Para a teoria dos grafos uma "estratégia gulosa" é conveniente já que sendo P um menor caminho entre 2 vértices U e V, todo sub-caminho de P é um menor caminho entre 2 vértices pertencentes ao caminho P, desta forma construímos os melhores caminhos dos vértices alcançáveis pelo vértice inicial determinando todos os melhores caminhos intermediários. Nota: diz-se 'um menor caminho' pois caso existam 2 'menores caminhos' apenas um será descoberto.

O algoritmo considera um conjunto S de menores caminhos, iniciado com um vértice inicial I. A cada passo do algoritmo busca-se nas adjacências dos vértices pertencentes a S aquele vértice com menor distância relativa a I e adiciona-o a S e, então, repetindo os passos até que todos os vértices alcançáveis por I estejam em S. Arestas que ligam vértices já pertencentes a S são desconsideradas.

O algoritmo de Dijkstra não consegue encontrar o menor caminho em um grafo com pesos negativos. Para esse propósito, pode-se usar o algoritmo de Floyd-Warshall, que consegue descobrir a menor distância entre todos os pares de vértices de qualquer grafo sem ciclos com peso negativo em uma complexidade de tempo O(V³). Se o problema não exigir o cálculo da distância entre todos os pares de vértices ou se existirem ciclos com peso negativo, pode-se aplicar o algoritmo de Bellman-Ford, com complexidade de tempo O(V*E). Em uma árvore, é possível encontrar a distância entre um vértice inicial e todos os outros vértices em tempo O(V+E), utilizando busca em profundidade (também conhecida como DFS). Em um grafo cujas arestas têm todas o mesmo peso, pode-se encontrar a distância entre um vértice inicial e todos os outros vértices, para um grafo qualquer, em O(V+E), utilizando busca em largura (também conhecida como BFS). O processo utilizado no algoritmo de Dijkstra é bastante similar ao processo usado no algoritmo de Prim. O propósito deste último, entretanto, é encontrar a árvore geradora mínima que conecta todos os nós de um grafo.

Algoritmo de Bellman-Ford

O Algoritmo de Bellman-Ford é um algoritmo de busca de caminho mínimo em um dígrafo ponderado, ou seja, cujas arestas têm peso, inclusive negativo. O Algoritmo de Dijkstra resolve o mesmo problema, em um tempo menor, porém exige que todas as arestas tenham pesos positivos. Portanto, o algoritmo de Bellman-Ford é normalmente usado apenas quando existem arestas de peso negativo.

Algoritmo A*

Algoritmo A* é um algoritmo para Busca de Caminho. Ele busca o caminho em um grafo de um vértice inicial até um vértice final. Ele é a combinação de aproximações heurísticas como do algoritmo Best-first Search e da formalidade do Algoritmo de Dijkstra.

O algoritmo foi descrito pela primeira vez em 1968 por Peter Hart, Nils Nilsson, e Bertram Raphael. Na publicação deles, ele foi chamado de algoritmo A; usando este algoritmo com uma heurística apropriada atinge-se um comportamento ótimo, e passou a ser conhecido por A*.

Sua aplicação vai desde aplicativos para encontrar rotas de deslocamento entre localidades a resolução de problemas, como a resolução de um quebra-cabeças. Ele é muito usado em jogos.

Algoritmo de  Johnson

Algoritmo de Johnson é uma forma de encontrar o menor caminho entre dois pontos. Ele permite que algumas bordas tenham número negativo, mas ciclos negativos não devem existir. Este algoritmo trabalha com base no Algoritmo de Bellman-Ford, para computar uma transformação de um grafo de entrada, que remove todos os pesos negativos, permitindo o uso do algoritmo de Dijkstra no grafo transformado. Recebe esse nome em homenagem a Donald B. Johnson, o primeiro a descrevê-lo, em 1977.

Algoritmo de Plim

O algoritmo de Prim é um algoritmo guloso (greedy algorithm) empregado para encontrar uma árvore geradora mínima (minimal spanning tree) num grafo conectado, valorado e não direcionado. Isso significa que o algoritmo encontra um subgrafo do grafo original no qual a soma total das arestas é minimizada e todos os vértices estão interligados. O algoritmo foi desenvolvido em 1930 pelo matemático Vojtěch Jarník e depois pelo cientista da computação Robert Clay Prim em 1957 e redescoberto por Edsger Dijkstra em 1959.

Outros algoritmos conhecidos para encontrar árvores geradoras mínimas são o algoritmo de Kruskal e algoritmo de Boruvka. No entanto estes algoritmos podem ser empregados em grafos desconexos, enquanto o algoritmo de Prim precisa de um grafo conexo.

O Problema a ser resolvido

Imagine que uma transportadora decidiu alavancar as suas entregas e fez uma promoção de 50% em todas as entregas da cidade A até a cidade F. Para que ela não tenha prejuízo ela terá sempre que percorrer o menor caminho entre as cidades. Como fazer isso?

·         Problema:

o   Obter Caminhos interligando Vértices de um Grafo, cujo comprimento (Custo) seja Mínimo.

·         Implementações:

o   Algoritmo de Dijkstra

·         Aplicação:

o   Redes de Computadores (Percurso entre Roteadores)

o   Tráfego Urbano.

o   Sistemas Rodoviários, Ferroviários e Aéreos,

o   Importante para vários outros problemas

Será resolvido com o algoritmo de Dijkstra melhor algoritmo conhecido aplicado a grafos com pesos não negativos. Passo-a-passo a seguir:

•          Encontra os caminhos mais curtos de acordo com a distância a uma dada fonte

•           Primeiro,encontra o caminho mais curto da fonte ao vértice mais próximo e assim por diante.

•           Em geral, antes da i-ésima iteração iniciar, o algoritmo já encontrou os menores caminhos para os outros i-1 vértices próximos da fonte

•          Estes vértices, a fonte, e as arestas dos caminhos mais curtos formam uma subárvore Ti.

•           Como todos os pesos das arestas são não negativos, o vértice seguinte mais próximo da fonte pode ser encontrado dentre os vértices adjacentes aos vértices de Ti.

•           Para identificar o i-ésimo vértice mais próximo, o algoritmo calcula, para cada vértice candidato u, a soma da distância ao vértice da árvore v mais próximo e o comprimento dv do caminho mais curto da fonte à v e então seleciona o vértice cuja soma seja a menor.

•            Cada vértice possui duas etiquetas:

•          Um valor numérico d que indica o comprimento do caminho mais curto da fonte ao vértice encontrado pelo algoritmo até o momento. Quando um vértice for adicionado a árvore, d indica o comprimento do caminho mais curto da fonte até o vértice.

•          A outra etiqueta indica o nome do próximo ao último vértice neste caminho, i.e., o pai do vértice na árvore sendo construída.

•          Com estas etiquetas, encontrar o vértice mais próximo u* seguinte torna-se uma tarefa simples que consiste em encontrar o vértice candidato com o menor valor de d.

•           Após identificado o vértice u* a ser adicionado a árvore, as seguintes operações devem ser realizadas:

•           Mover o vértice u* do vértice candidato para o conjunto dos vértices da árvore

•          Para cada vértice candidato remanescente u que estiver conectado a u* por uma aresta de pesos(u*,u) tal que du* + w(u*,u) < dw, atualize as etiquetas de u por u* e du* + w(u*,u) respectivamente.

•           Dijkstra compara comprimento de caminhos

•          Algoritmo de Dijkstra

•          topologia da rede, custos dos enlaces conhecidos por todos os nós

•          realizado através de “difusão do estado dos enlaces”

•          todos os nós têm mesma info.

•          calcula caminhos de menor custo de um nó (“origem”) para todos os demais

•          gera tabela de rotas para aquele nó

•          iterativo: depois de k iterações, sabemos menor custo p/ k destinos

•          Notação:

•          c(i,j): custo do enlace do nó i ao nó j. custo é infinito se não forem vizinhos diretos

•          D(V): valor corrente do custo do caminho da origem ao destino V

•          p(V): nó antecessor no caminho da origem ao nó V

•          N: conjunto de nós cujo caminho de menor custo já foi determinado

Resumo:

1         Inicialização:

2         N = {A}

3         para todos os nós V

4         se V for adjacente ao nó A

5         então D(V) = c(A,V)

6         senão D(V) = infinito

7         Repete

8         determina W não contido em N tal que D(W) é o mínimo

9         adiciona W ao conjunto N

10     atualiza D(V) para todo V adjacente ao nó W e ainda não em N:

11     D(V) = min( D(V), D(W) + c(W,V) )

12     /* novo custo ao nó V ou é o custo velho a V ou o custo do

13     menor caminho ao nó W, mais o custo de W a V */

14     até que todos nós estejam em N

A eficiência do algoritmo de Dijkstra depende das estruturas de dados usadas na implementação da fila de prioridade e do grafo.

Este algoritmo parte de uma estimativa inicial para o custo mínimo e vai sucessivamente ajustando esta estimativa. Ele considera que um vértice estará fechado quando já tiver sido obtido um caminho de custo mínimo do vértice tomado como raiz da busca até ele. Caso contrário ele dito estar aberto.

Referencia

•          CORMEN,T.H.; LEISERSON, C.E. and RIVEST, R.L. Introduction to Algorithms. Cambridge: MIT Press, 1996.

•          Algoritmo de Dijkstra Disponível em: <http://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra>  acesso em: 10/12/2013.

•          Algoritmo de Dijkstra para cálculo do Caminho de Custo Mínimo Disponível em: < http://www.inf.ufsc.br/grafos/temas/custo-minimo/dijkstra.html> acesso em: 11/12/2013.