Algoritmo de Dijkstra

Você recebe um grafo, direto ou indireto, com pesos em suas arestas e que possui $n$ vértices e $m$ arestas. Os pesos de todas as arestas são não-negativos e definimos um vértice inicial $s$. Este artigo descreve como encontrar os comprimentos dos caminhos mais curtos de um vértice inicial $s$ para todos os outros vértices.

Esse problema também é chamado caminhos mais curtos de fonte única.

Algoritmo

Aqui está um algoritmo descrito pelo cientista da computação Edsger W. Dijkstra em 1959.

Iremos criar uma array $d[$ $]$ onde para cada vértice $v$ guardaremos o comprimento atual do caminho mais curto, de $s$ para $v$, em $d[v]$. Inicialmente $d[s] = 0$, e para todos os outros vértices esse comprimento é igual ao infinito. Na implementação, um número suficientemente grande (garantindo que seja maior que qualquer comprimento de caminho possível) é escolhido como o infinito.

$$d[v] = \infty,~ v \ne s$$

Além do mais, mantemos uma array Boolean $u[$ $]$ que armazena para cada vértice $v$ se ele foi visitado/marcado. Inicialmente todos os vértices não estão marcados:

$$u[v] = {\rm false}$$

O algoritmo de Dijkstra é executado por $n$ iterações. Em cada iteração, um vértice $v$ é escolhido como vértice não marcado que tem o menor valor $d[v]$:

Evidentemente, na primeira iteração o vértice inicial $s$ será selecionado.

O vértice selecionado $v$ é marcado. Em seguida, do vértice $v$, aproximações (relaxations) são performadas: todas as arestas da forma $(v,\text{to})$ são consideradas, e para cada vértice $\text{to}$ o algoritmo tenta aprimorar o valor $d[\text{to}]$. Se o comprimento da aresta atual for igual a $len$:

$$d[\text{to}] = \min (d[\text{to}], d[v] + len)$$

Depois que todas essas arestas são consideradas, a iteração atual termina. Finalmente, depois de $n$ iterações, todos os vértices serão marcados, e o algoritmo termina. Afirmamos que os valores encontrados $d[v]$ são os comprimentos dos caminhos mais curtos de $s$ para todos os vértices $v$.

Observe que, se alguns vértices são inacessíveis, do vértice inicial $s$, os valores $d[v]$ irão permanecer como infinito. Obviamente, as últimas iterações do algoritmo escolherão esses vértices, mas nenhum trabalho útil será feito para eles. Portanto, o algoritmo pode ser parado assim que o vértice selecionado tiver uma distância infinita.

Restaurando Caminhos Curtos

Geralmente, é necessário conhecer não apenas os comprimentos dos caminhos mais curtos, mas o próprio caminho curto de um vértice inicial $s$ para outros vértices. Manteremos uma array de predecessores $p[$ $]$ na qual para cada vértice $v \ne s$, $p[v]$ será o penultimo vértice no caminho mais curto de $s$ para $v$. Aqui usamos o fato de que, se tomarmos o caminho mais curto para algum vértice $v$ e removermos $v$ desse caminho, teremos um caminho que termina no vértice $p[v]$, e esse caminho será o mais curto para o vértice $p[v]$. Esse array de predecessores pode ser usado para restaurar o caminho mais curto para qualquer vértice: começando com $v$, repetidamente pegue o predecessor do vértice atual até atingir o vértice inicial $s$ para obter o caminho mais curto com vértices listados em ordem reversa. Então, o caminho mais curto $P$ para o vértice $v$ é igual a:

$$P = (s, \ldots, p[p[p[v]]], p[p[v]], p[v], v)$$

Construindo essa array de predecessores é bem simples: para cada iteração, i.e. para algum vértice selecionado $v$, haverá uma melhora na distância para algum vértice $\text{to}$, atualizamos o vértice predecessor para $\text{to}$ com o vértice $v$:

$$p[\text{to}] = v$$

Prova

A principal afirmação, na qual a certeza do algoritmo de Dijkstra se encontra, se baseia no seguinte:

Depois que passamos pelo vértice $v$ ou que qualquer vértice $v$ seja marcado, a distância atual $d[v]$ é a mais curta, e não irá mais mudar.

A prova é feita por indução. Para a primeira iteração essa declaração é óbvia: o único vértice marcado é $s$, e a distância para ele é $d[s] = 0$ que é o menor caminho para $s$. Agora suponha que essa declaração é verdadeira para todas as iterações prévias, i.e. para todos os vértice previamente marcados; vamos provar que ela não será negada depois que a iteração atual se complete. $v$ é o vértice selecionado na iteração, i.e. $v$ é vértice que o algoritmo irá marcar. Precisamos provar que $d[v]$ é realmente igual ao comprimento do menor caminho para ele $l[v]$.

Considere o caminho mais curto $P$ para o vértice $v$. Esse caminho pode ser dividido em duas partes: $P_1$ que consiste apenas de nós marcados (pelo menos o vértice inicial $s$ é parte de $P_1$), e o resto do caminho $P_2$ (pode incluir um vértice marcado, mas sempre começa com um vértice não marcado). Vamos denotar o primeiro vértice de $P_2$ como $p$, e o último vértice do caminho $P_1$ como $q$.

Primeiro provamos nossa declaração para $p$, i.e. vamos provar que $d[p] = l[p]$. Isso é quase óbvio: em uma das iterações prévias escolhemos o vértice $q$ e performamos uma iteração sobre ele. Desde que o caminho mais curto para $p$ é o caminho mais curto para $q$ $+$ a aresta $(p,q)$, a iteração de $q$ iguala o valor $d[p]$ para o caminho mais curto $l[q]$.

Desde que o peso das arestas não sejam negativos, o comprimento do caminho mais curto $l[p]$ (que acabamos de provar que é igual a $d[p]$) não excede o comprimento $l[v]$ do caminho mais curto para o vértice $v$. Dado que $l[v] \le d[v]$ (porque o algoritmo de Dijkstra não pôde encontrar um caminho mais curto que o mais curto possível(triste, não?)), conseguimos a inequação:

$$d[p] = l[p] \le l[v] \le d[v]$$

Por outro lado, ja que ambos os vértices $p$ e $v$ não foram marcados, e a iteração atual escolhe o vértice $v$, não $p$, temos outra inequação:

$$d[p] \ge d[v]$$

Dessas duas inequações, podemos concluir que $d[p] = d[v]$, e então:

$$d[v] = l[v]$$

Q.E.D.

Implementação

Dijkstra executa $n$ iterações. Em cada iteração ele marca um vértice $v$ com o menor valor possível $d[v]$, marca e checa todas as arestas $(v, \text{to})$ tentando aprimorar(minimizar) o valor $d[\text{to}]$.

O tempo de execução do algoritmo consiste em:

Para uma implementação simples dessas operações em cada iteração a procura do vértice requer $O(n)$ operações, e cada aprimoramento pode ser performado em $O(1)$. Consequentemente, o resultado do comportamento do algoritmo é:

$$O(n^2+m)$$

Essa complexidade é optmizada para grafos densos(dense graphs, muitas conexões), i.e. quando $m \approx n^2$. Entretanto em grafos esparsos(sparse graph), quando $m$ é bem menor que o número máximo de arestas $n^2$, o problema pode ser resolvido em complexidade $O(n \log n + m)$. O algoritmo e sua implementação podem ser encontrados Dijkstra em grafos esparsos.

const int INF = 1000000000;     
vector<vector<pair<int, int>>> adj;   //grafo 

void dijkstra(int s, vector<int> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);                 //array de distancias minimas
    p.assign(n, -1);                  //array de predecessores
    vector<bool> u(n, false);   //marcados

    d[s] = 0;                        //distancia para o vertice inicial = 0
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (!u[j] && (v == -1 || d[j] < d[v]))   //encontrando o nó v com d[v] mínimo(com a menor distancia ate ele)
                v = j;
        }

        if (d[v] == INF)   //vértice inacessível
            break;

        u[v] = true;
        for (auto edge : adj[v]) {     //checando arestas do nó selecionado
            int to = edge.first;      //próximo nó
            int len = edge.second;    //comprimento da aresta atual

            if (d[v] + len < d[to]) {     //atualizando distancia minima para o proximo vertice
                d[to] = d[v] + len;
                p[to] = v;                   //atualizando predecessor
            }
        }
    }
}

Aqui o grafo $\text{adj}$ é armazenado como uma lista de adjacência: para cada vértice $v$ $\text{adj}[v]$ contém a lista de arestas vindas desse vértice, i.e. a lista do par pair<int,int> onde o primeiro elemento no par é o vértice no final da aresta, e o segundo elemento é o peso da aresta.

A função armazena o vértice inicial $s$ e dois vetores que serão usados para retornar valores.

Primeiramente, o código inicializa arrays: distâncias $d[$ $]$, booleanos(indicação de marcados) $u[$ $]$ e predecessores $p[$ $]$. Performando $n$ iterações. Em cada iteração o vértice $v$ é selecionado/marcado na qual ele possui a mínima distância $d[v]$ dentre todos os vértices não marcados. Se a distância para selecionar $v$ é igual ao infinito, o algoritmo para. Caso contrário o vértice é marcado, e todas as arestas que saem desse vértice são checadas. Se um aprimoramento dentre as arestas é possível (i.e. distância $d[\text{to}]$ pode ser aprimorada/minimizada), a distância $d[\text{to}]$ e o predecessor $p[\text{to}]$ são atualizados.

Depois de performar todas as iterações, a array $d[]$ armazena os comprimentos dos caminhos mais curtos para todos os vértices, e a array $p[]$ armazena os predecessores de todos os vértices (exceto o vértice inicial $s$). O caminho para qualquer vértice $t$ pode ser restaurado da seguinte maneira:

vector<int> restore_path(int s, int t, vector<int> const& p) {
    vector<int> path;

    for (int v = t; v != s; v = p[v])
        path.push_back(v);
    path.push_back(s);

    reverse(path.begin(), path.end());
    return path;
}

De forma similar, utilizando uma priority queue porém sem a utilização da array de predecessores e booleanos, a implementação pode ser feita da seguinte forma:

const int INF = 1000000007;
const int maxn = 10000009;
vector<pair<int,int>> v[maxn];  // grafo
int dis[maxn];       // array com as distâncias mínimas
int n;               // número de nós
 
void inf(){                          //infinitar as distâncias
	for(int i = 0; i < n; ++i){
		dis[i] = INF;
	}
}
 
void aresta(int a, int b, int c){    //aresta com peso
	v[a].push_back({b,c});
	v[b].push_back({a,c});
}
 
void dijkstra(int s){               //algoritmo de dijkstra
	inf();
 
	dis[s] = 0;
	priority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
	pq.push({0, s});
 
	while(!pq.empty()){
		auto f = pq.top();
		pq.pop();
		if(dis[f.second] < f.first) continue;    //dis[node] < dis[atual sendo checada] (para aprimoramento),i.e se esse no ja tiver uma distancia menor  
		for(auto e : v[f.second]){               //checar arestas 
			if(f.first + e.second < dis[e.first]){   //e.second = c (peso da aresta) | e.first = próximo nó 
				dis[e.first] = f.first + e.second;   //atualizando a distanca minima do próximo nó (aprimoramento)
				pq.push({dis[e.first], e.first});    
			}
		}
	}
}

Referências

Problemas