Algoritmo de Dijkstra

Publicado: 17/08/2011 por ॐ MZ.. em Engenharia da Computação, Notícias, Videos
Tags:, , ,

O algoritmo de Dijkstra, cujo nome se origina de seu inventor, o cientista da computação Edsger Dijkstra, 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érticeis 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.

Um exemplo prático do problema que pode ser resolvido pelo algoritmo de Dijkstra é: alguém precisa se deslocar de uma cidade para outra. Para isso, ela dispõe de várias estradas, que passam por diversas cidades. Qual delas oferece uma trajetória de menor caminho?

Algoritmo


1º passo: iniciam-se os valores:
para todo v ∈ V[G]
     d[v]← ∞
     π[v] ← nulo
d[s] ← 0
V[G]
é o conjunto de vértices(v) que formam o Grafo G. d[v] é o vetor de distâncias de s até cada v.
Admitindo-se a pior estimativa possível, o caminho infinito. π[v] identifica o vértice de onde se origina uma conexão
até v de maneira a formar um caminho mínimo.

2º passo: temos que usar dois conjuntos: S, que representa todos os vértices v onde d[v] já contem o custo do menor caminho e Q que contem todos os outros vértices.
Q ← V[G]

3º passo: realizamos uma série de relaxamentos das arestas, de acordo com o código:
enquanto Q ≠ ø
         u ← extraia-mín(Q)
         S ← S ∪ {u}
         para cada v adjacente a u
              se d[v] > d[u] + w(u, v)          //relaxe (u, v)
                 então d[v] ← d[u] + w(u, v)
                       π[v] ← u w(u, v)
é o peso(weight) da aresta que vai de u a v.u e v são vértices quaisquer e s é o vértice inicial.extraia-mín(Q),
pode usar um heap de mínimo ou uma lista de vértices onde extrai-se o elemento u com menor valor d[u]

fonte wikipedia

comentários
  1. Tamara disse:

    ahhhh agora entendiiiiii

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s