Algoritmo de dijkstra

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (269 palavras )
  • Download(s) : 0
  • Publicado : 18 de março de 2013
Ler documento completo
Amostra do texto
RELATÓRIO DO ALGORITMO DE DIJKSTRA

O funcionamento do algoritmo
Definimos inicio e fim como os vértices onde o caminho deve começar e terminar,respectivamente.
Seja foi o conjunto dos vértices do grafo (ou digrafo) que já foram processados pelo algoritmo. Se um vértice pertencer a foi, então necessariamente seucusto mínimo já foi calculado.
Seja também custo[i] a menor distância de inicio até o vértice i.
Também definimos uma matriz de adjacências, grafo[u][v],indicando o custo da aresta de u a v.

No início do algoritmo determinamos foi = {inicio} e custo[inicio] = 0. A ideia é expandirmos o conjunto foi até englobar ovértice fim.
A cada passo atualizamos as distâncias custo[i] dos vértices que não estão no conjunto foi, ou seja, pegamos o último vértice inserido em foi, olhamosseus vizinhos, e verificamos se custo[vizinho] > custo[atual] + grafo[atual][vizinho]. Isto é, se o custo para chegar até vizinho pode ser reduzidocaminhando de atual até vizinho. Se sim, então reduzimos custo[vizinho], atualizando seu valor para custo[vizinho] = custo[atual] + grafo[atual][vizinho]. Este passomuitas vezes é chamado de relaxamento.
Após esse passo, verificamos entre todos os vértices que não estão no conjunto foi e selecionamos o que tem menor custo[i].Este vértice já está com a menor distância
possível, ou seja, seu caminho de menor custo já foi determinado! Assim, incluímos esse vértice em foi, e voltamospara o processo de atualizar os vizinhos, repetindo o loop até que o vértice fim seja aquele a ser incluído em foi.
O algorítmo encontra-se anexado na pasta ASA.
tracking img