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:
- 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$$.
- 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.
- 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)$$.
- 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: