Algoritmo de Dijkstra

Keywords: Algoritmo de Dijkstra, Ciência da computação, Edsger Dijkstra, Função, Grafo, Par ordenado, Trajetória

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 para um grafo dirigido com arestas de peso não negativo.

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?

Definições

Consideremos um grafo dirigido G e cujas arestas possuem um peso. V é o conjunto de vértices de G. O vértice de origem é denominado s. As arestas são representadas pelo par ordenado (u, v) ou seja, a conexão entre o vértice u e o vértice v. O conjunto das arestas de G é E. O peso de cada aresta é definido pela função w: E → R₊.

δ(s, v) é o menor caminho de entre s e um vértice v ∈ E qualquer . Portanto, δ(s, v) é a menor soma possível dos pesos das arestas que compõem um caminho entre s e v, ou infinito se não existir caminho entre s e v. Na execução do algoritmo também é necessário um d[v] chamado de estimativa de menor caminho, é o limite máximo estimado para δ(s, v) em um determinado instante. π[v] é o vértice predecessor de v.

Algoritmo

1º passo: iniciam-se os valores:

para todo v ∈ V[G]
      d[v]← ∞ 
      π[v] ← nulo
 d[s] ← 0

Admitindo-se a pior estimativa possível, o caminho infinito.

2º passo: temos que usar dois conjuntos: S, que representa todos os vértices v tal que d[v] = δ(s, v), e o Q, simbolizando 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

No final do algoritmo teremos o menor caminho entre s e qualquer outro vértice de G.

Dijkstra