Algoritmo de Dijkstra
Origem: Wikipédia, a enciclopédia livre.
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 em grafo 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.
Um exemplo prático de 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?
[editar] Definições
[editar] 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.
- 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 ser um heap de mínimo ou uma lista ordenada de vértices onde obtém-se o menor elemento, ou qualquer estrutura do tipo.
No final do algoritmo teremos o menor caminho entre s e qualquer outro vértice de G.
[editar] Ligações externas
- ((es)) Algoritmo de Dijkstra em C++
- ((en)) [1] - NIST
