Dijkstra

Aula por Lúcio Cardoso

Imagine que temos um grafo com $N$ vértices e $M$ arestas, cada uma delas contendo um peso (um valor positivo arbitrário). Além disso, é dado um vértice $S$ qualquer do grafo. O problema do Menor Caminho consiste em calcular, para cada vértice $V$, a menor distância de $S$ para $V$, isto é, a menor soma possível de pesos de arestas que formem um caminho de $S$ para $V$.

Como um exemplo, se definirmos a origem $S$ como o vértice $1$ do grafo acima, teremos que:

• O menor caminho para o vértice $1$ é $0$.
• O menor caminho para o vértice $2$ é $4$.
• O menor caminho para o vértice $3$ é $7$.
• O menor caminho para o vértice $4$ é $5$.
• O menor caminho para o vértice $5$ é $1$.

Algoritmo de Dijkstra

O algoritmo de Dijkstra é usado para resolver o problema citado acima. Ele consiste das seguintes etapas:

1. Inicialmente, marque todos os vértices do grafo como não visitados. Além disso, defina a distância atual para $S$ (origem) como $0$ e para todos os outros vértices como $\infty$.
2. Encontre, dentre os vértices não visitados, aquele com menor distância atual. Chame-o de $U$ e marque-o como visitado. Assim, a distância atual de $U$ é, de fato, a sua menor distância para $S$ e $U$ não será visitado novamente.
3. Para todo vizinho de $V$ de $U$, cheque se $d_{at}(S, V) > d(S, U) + w(U, V)$, onde $d_{at}(S, V)$ é a distância atual de $V$, $d(S, U)$ é o menor caminho de $U$ e $w(U, V)$ é o peso da aresta que liga $U$ e $V$. Se sim, atualize a distância atual de $V$ para $d(S, u) + w(u, v)$.
4. Repita as etapas $2$ e $3$ até que todos os vértices do grafo estejam marcados.

Por que o Algoritmo de Dijkstra funciona?

Suponha que em um momento qualquer do algoritmo, o vértice $V$ é o vértice não marcado mais próximo de $S$, ou seja, aquele cujo menor caminho para $S$ é mínimo. Perceba que o menor caminho de $S$ para $V$ é composto pelo menor caminho de $S$ para algum vértice $U$ seguido de uma aresta de $U$ para $V$. Como as arestas tem pesos positivos, o menor caminho de $U$ é certamente menor que o menor caminho de $V$. Logo, como $V$ é definido como o vértice não marcado de menor caminho mínimo, teremos que o vértice $U$ certamente já foi marcado. Porém, assim que $U$ for marcado, a etapa $3$ do algoritmo será realizada em seus vizinhos, e em particular, a distância atual de $V$ será atualizada para $d(S, U) + w(U, V)$, que é exatamente o menor caminho de $V$!

Queremos agora provar que o vértice escolhido na etapa $2$ é exatamente o vértice $V$. Suponha que o vértice não marcado de menor distância atual é um vértice $W \neq V$. Então, teremos que

$d_{at}(S, W) < d_{at}(S, V)$.

Como mostrado acima,

$d_{at}(S, V) = d(S, V) \implies d_{at}(S, W) < d(S, V)$.

Mas

$d(S, W) \leq d_{at}(S, W)$ (por definição) $\implies d(S, W) < d(S, V)$

uma contradição, já que $V$ foi definido como o vértice não marcado de menor caminho mínimo. Logo, $V$ será o vértice escolhido na etapa $2$ do algoritmo, e além disso, sua distância atual será igual à sua menor distância para $S$, o que conclui a prova.

Para implementar o algoritmo de Dijkstra, representaremos o nosso grafo como uma Lista de Adjacência. Além disso, vamos usar uma Fila de Prioridade que irá guardar pares da forma $(d_{at}(v), v)$, ou seja, a fila será ordenada de maneira crescente pela distância atual de cada vértice. Isso será de grande utilidade para realizarmos a etapa $2$ de maneira eficiente.

Observação

O algoritmo apresentado acima funciona em grafos com arestas de pesos não-negativos e não funciona caso alguma delas tenha peso negativo.

Confira o código abaixo: