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
