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:

	// Curso Noic - Algoritmo de Dijkstra
	#include <bits/stdc++.h>
	using namespace std;
	typedef pair<int, int> pii;
	const int maxn = 1e5+10;
	const int inf = 1e9+10;
	// quantidade de vértices e arestas
	int n, m;
	// distância Atual de cada vértice
	int dist[maxn];
	// vetor que irá marcar os vértices visitados
	bool mark[maxn];
	// lista de adjacência que guarda um par (vértice, peso)
	vector<pii> grafo[maxn];
	void dijkstra(int S)
	{
	// primeira etapa do algoritmo
	for (int i = 1; i <= n; i++)
	dist[i] = inf;
	dist[S] = 0;
	// fila de prioridade para guardar a distância atual de cada vértice em ordem crescente
	priority_queue<pii, vector<pii>, greater<pii>> fila;
	// inicialmente, inserimos apenas a origem
	fila.push({0, S});
	// quando todos os vértices forem marcados, a fila ficará vazia, e nesse momento o algoritmo para
	while (!fila.empty())
	{
	// segunda etapa do algoritmo
	int u = fila.top().second;
	fila.pop();
	// se U já foi marcado, apenas o ignoramos
	if (mark[u])
	continue;
	// marcamos U
	mark[u] = 1;
	for (auto V: grafo[u])
	{
	int v = V.first, w = V.second;
	// terceira etapa do algoritmo
	if (dist[v] > dist[u] + w)
	{
	// atualizamos a distância atual de V e a inserimos na fila
	dist[v] = dist[u] + w;
	fila.push({dist[v], v});
	}
	}
	}
	// No fim do algoritmo, o vetor 'dist' possuirá o menor caminho para
	// todos os vértices do grafo
	}

view raw noic-dijkstra.cpp hosted with by GitHub