Resumo O que é o Algoritmo 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.

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.

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