Algoritmo de Dijkstra

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Esta página ou secção cita fontes confiáveis e independentes, mas que não cobrem todo o conteúdo (desde Agosto de 2013). Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Material sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
Algoritmo de Dijkstra

Execução do algoritmo de Dijkstra
classe Algoritmo de busca
estrutura de dados Grafo
complexidade pior caso
Algoritmos

O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959[1][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 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 de Dijkstra[editar | editar código-fonte]

  • 1º passo: iniciam-se os valores:
para todo v ∈ V[G]
     d[v]← ∞ 
     π[v] ← -1
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 o conjunto Q, cujos vértices ainda não contém o custo do menor caminho d[v] determinado.
Q ← V[G]
  • 3º passo: realizamos uma série de relaxamentos das arestas, de acordo com o código:
enquanto Q ≠ ø
         u ← extrair-mín(Q)                     //Q ← Q - {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. ffd extrair-mín(Q), pode usar um heap de mínimo ou uma lista de vértices onde se extrai o elemento u com menor valor d[u].

No final do algoritmo teremos o menor caminho entre s e qualquer outro vértice de G. O algoritmo leva tempo O(m + n log n) caso seja usado um heap de Fibonacci, O(m log n) caso seja usado um heap binário e O(n²) caso seja usado um vetor para armazenar Q.

Problemas relacionados[editar | editar código-fonte]

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. O BFS pode ser visto como um caso especial do algoritmo de Dijkstra em grafos não dirigidos, onde a fila de prioridade assume o comportamento FIFO.

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]

Referências

  1. Dijkstra, Edsger; Thomas J. Misa, Editor (2010-08). «An Interview with Edsger W. Dijkstra». Communications of the ACM [S.l.: s.n.] 53 (8): 41–47. doi:10.1145/1787234.1787249. «What is the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path which I designed in about 20 minutes. One morning I was shopping with my young fianceé, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path.» 
  2. Dijkstra 1959