Dado um grafo G = (V, E) e um vértice inicial s ∈ V, é possível calcular os caminhos:
- De s a algum u | u ∈ V
- De s a todos os outros vértices pertencentes a V
- De todos os vértices a todos os vértices pertencentes a V
O que faz sentido, visto que ao executar um algoritmo que encontra um caminho específico também se descobrem, ao longo do processo, várias informações a respeito dos demais caminhos, de modo que um algoritmo que encontre vários caminhos possa ser mais otimizado que executar diversas vezes um algoritmo que calcula um caminho só.
O algoritmo de Dijkstra se enquadra na segunda categoria.
Relembrando: um caminho entre dois vértices conectados é definido pelo percurso de menor comprimento entre tais vértices.
Quando um grafo não possui arestas valoradas, o cálculo de distâncias pode ser realizado através de uma simples busca em largura. Quando as arestas são valoradas, o problema pode ser resolvido com Dijkstra, desde que não hajam arestas de custo negativo. Para grafos com presença de custos negativos, uma modificação no algoritmo de Dijkstra que eleva sua ordem de complexidade se faz necessária. Entenderemos o motivo desta limitação mais tarde.
- aberto ← V
- para todo (v ∈ V)
- distancia[v] ← ∞
- anterior[v] ← -1
- distancia[s] ← 0
- enquanto aberto ≠ ø
- u ← min(aberto)
- aberto ← u
- para cada v adjacente a u faça
- se (distancia[v] > distancia[u] + w(u, v)) então
- distancia[v] ← distancia[u] + w(u, v)
- anterior[v] ← u
A saída consiste em dois vetores: distancia e anterior, ambos de tamanho |V| (linhas 2-4). O vetor distancia armazena a distância de s aos demais vértices. Quando não se conhece a distância, armazena-se ∞, geralmente representado computacionalmente por INT_MAX. O vetor anterior armazena o vértice imediatamente anterior a cada vértice v no caminho (s, v). Deste modo, o vetor anterior representa uma árvore de caminhamento mínimo, onde o caminho de v a s é definido por (v, anterior(v), anterior(anterior(v)), ..., s).
Este algoritmo se baseia sobre 3 ideias:
1 - Conjunto de vértices abertos e fechados.
Este algoritmo se baseia sobre 3 ideias:
1 - Conjunto de vértices abertos e fechados.
Ao longo do algoritmo alguns percursos serão gravados nestes vetores sem que tenhamos certeza de que são, de fato, os caminhos procurados, ou seja, de que não serão atualizados novamente no futuro. Os vértices aos quais possuímos um caminho incerto se mantém inseridos no conjunto "aberto". Quando se obtém a certeza de que um caminho aberto é, de fato, o caminho correto, ele é removido do conjunto aberto, e chamamos este vértice de "fechado", embora este conjunto não exista explicitamente. O conjunto aberto, inicia com todos os vértices de V (linha 1).
A princípio, são inicializados os vetores distancia e anterior com ∞ e -1, respectivamente, pois nenhum percurso foi encontrado ainda (linhas 2 a 4), e atribuímos 0 à distancia de s até s (linha 5), pois sabemos de antemão que a distância de um vértice a ele próprio é sempre zero.
Após as inicializações, todo o algoritmo está compreendido dentro de uma estrutura de repetição que só termina quando não restar mais nenhum vértice definido aberto, ou seja, quando conhecermos com exatidão os caminhos a todos os vértices, tal qual nosso objetivo.
2 - Como encontrar percursos melhores que o já conhecido:
Se temos um percurso de A a B, um percurso de B a C e um percurso de A a C, e a soma dos comprimentos dos percursos de A a B e de B a C é menor que o comprimento do percurso que conhecemos de A a C, então podemos descartar o percurso conhecido de A a C e substituir ele pelo percurso resultante da união dos percursos de A a B e de B a C, pois este é melhor.
2 - Como encontrar percursos melhores que o já conhecido:
Se temos um percurso de A a B, um percurso de B a C e um percurso de A a C, e a soma dos comprimentos dos percursos de A a B e de B a C é menor que o comprimento do percurso que conhecemos de A a C, então podemos descartar o percurso conhecido de A a C e substituir ele pelo percurso resultante da união dos percursos de A a B e de B a C, pois este é melhor.
3 - Se um percurso desconhecido A contém um percurso conhecido B, A ≥ B.
Se todas as arestas tiverem custo não negativo, então se um percurso A contém um percurso B (ou seja, possui todas as arestas que o percurso B possui), então A necessariamente possui comprimento igual ou maior que B.
O algoritmo percorre os vértices de tal modo que qualquer percurso de s a u, mesmo aqueles desconhecidos, contenha um percurso já conhecido (aberto ou não).
A cada iteração, será selecionado dentre os vértices abertos aquele de menor distância, que chamaremos de u (linha 7). Na primeira iteração, evidentemente, este será o próprio s (distância 0). Nas próximas iterações, u representará outros vértices.
Deste modo, se o percurso atual de s a u é o menor percurso conhecido de s a qualquer outro vértice, e qualquer outro percurso de s a u terá de conter um percurso que sabemos ser igual ou maior que o atual, então qualquer outro percurso terá comprimento igual ou maior que o atual, e portanto, podemos dizer que este vértice u, em qualquer iteração, não pertence mais a aberto (linha 8).
Esta é a grande sacada de Dijkstra que permite reduz a complexidade do algoritmo de |E| x |V| para |E|+|V|xlog|V|, mas ao mesmo tempo, faz com que o algoritmo não funcione caso exista uma aresta de custo negativo no grafo, pois se existir tal tipo de aresta, então um percurso A que contenha um percurso B não necessariamente possui comprimento igual ou maior que o de B.
A cada iteração, o algoritmo elege um vértice e o nomeia "v". Então, percorre todos os seus adjacentes verificando se a soma do comprimento do percurso do vértice inicial s ao vértice v com o peso da aresta de v ao seu adjacente é menor que o percurso já conhecido (gravado em distancia). Se for, v se torna o anterior do adjacente, esta soma de percursos se torna a nova distância (aplicação da ideia 2). Este caminho é dito aberto por enquanto, pois pode haver um melhor que este.
Inicialmente, todos os percursos começam com ∞, e qualquer aresta lida será menor que ∞ (por isso se usa INT_MAX).
O algoritmo inicia elegendo s como v. O custo de s a s é devidamente inicializado com 0. Em seguida, todos os adjacentes de s são lidos, e como seus custos são ∞, todos eles são atualizados em distancia (que se torna igual a 0 + peso da aresta entre s e o adjacente) e anterior (que se torna o próprio s). Deste modo, qualquer outro percurso de s a qualquer outro vértice do grafo terá, obrigatoriamente, que passar por algum desses caminhos em aberto, e portanto, devido à ideia 3, podemos afirmar que o menor percurso conhecido é necessariamente o melhor, e podemos fechá-lo.
O mesmo raciocínio é aplicado recursivamente ao vértice com menor custo até que todos os percursos estejam fechados, pois sabemos que se sempre elegermos o vértice de menor custo como v, então qualquer outro percurso de s a v conterá algum percurso já conhecido e sabidamente maior ou igual ao que já temos.
O algoritmo percorre os vértices de tal modo que qualquer percurso de s a u, mesmo aqueles desconhecidos, contenha um percurso já conhecido (aberto ou não).
A cada iteração, será selecionado dentre os vértices abertos aquele de menor distância, que chamaremos de u (linha 7). Na primeira iteração, evidentemente, este será o próprio s (distância 0). Nas próximas iterações, u representará outros vértices.
Deste modo, se o percurso atual de s a u é o menor percurso conhecido de s a qualquer outro vértice, e qualquer outro percurso de s a u terá de conter um percurso que sabemos ser igual ou maior que o atual, então qualquer outro percurso terá comprimento igual ou maior que o atual, e portanto, podemos dizer que este vértice u, em qualquer iteração, não pertence mais a aberto (linha 8).
Esta é a grande sacada de Dijkstra que permite reduz a complexidade do algoritmo de |E| x |V| para |E|+|V|xlog|V|, mas ao mesmo tempo, faz com que o algoritmo não funcione caso exista uma aresta de custo negativo no grafo, pois se existir tal tipo de aresta, então um percurso A que contenha um percurso B não necessariamente possui comprimento igual ou maior que o de B.
A cada iteração, o algoritmo elege um vértice e o nomeia "v". Então, percorre todos os seus adjacentes verificando se a soma do comprimento do percurso do vértice inicial s ao vértice v com o peso da aresta de v ao seu adjacente é menor que o percurso já conhecido (gravado em distancia). Se for, v se torna o anterior do adjacente, esta soma de percursos se torna a nova distância (aplicação da ideia 2). Este caminho é dito aberto por enquanto, pois pode haver um melhor que este.
Inicialmente, todos os percursos começam com ∞, e qualquer aresta lida será menor que ∞ (por isso se usa INT_MAX).
O algoritmo inicia elegendo s como v. O custo de s a s é devidamente inicializado com 0. Em seguida, todos os adjacentes de s são lidos, e como seus custos são ∞, todos eles são atualizados em distancia (que se torna igual a 0 + peso da aresta entre s e o adjacente) e anterior (que se torna o próprio s). Deste modo, qualquer outro percurso de s a qualquer outro vértice do grafo terá, obrigatoriamente, que passar por algum desses caminhos em aberto, e portanto, devido à ideia 3, podemos afirmar que o menor percurso conhecido é necessariamente o melhor, e podemos fechá-lo.
O mesmo raciocínio é aplicado recursivamente ao vértice com menor custo até que todos os percursos estejam fechados, pois sabemos que se sempre elegermos o vértice de menor custo como v, então qualquer outro percurso de s a v conterá algum percurso já conhecido e sabidamente maior ou igual ao que já temos.
