Algoritmo de Dijkstra
O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959,[1][2] soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional onde V é o número de vértices e E é o número de arestas. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford, que possui maior tempo de execução que o Dijkstra.
| Algoritmo de Dijkstra | |
|---|---|
 | |
| classe | Algoritmo de busca |
| estrutura de dados | Grafo |
| complexidade pior caso | |
| Algoritmos | |
O algoritmo considera um conjunto S de menores caminhos, iniciado com um vértice inicial I. A cada passo do algoritmo busca-se nas adjacências dos vértices pertencentes a S aquele vértice com menor distância relativa a I e adiciona-o a S e, então, repetindo os passos até que todos os vértices alcançáveis por I estejam em S. Arestas que ligam vértices já pertencentes a S são desconsideradas.
Um exemplo prático de problema que pode ser resolvido pelo algoritmo de Dijkstra é: alguém precisa se deslocar de uma cidade para outra. Para isso, ela dispõe de várias estradas, que passam por diversas cidades. Qual delas oferece uma trajetória de menor caminho?
Algoritmo de Dijkstra
- 1º passo: iniciam-se os valores:
para todo v ∈ V[G] d[v] ← ∞ π[v] ← -1d[s] ← 0
V[G] é o conjunto de vértices(v) que formam o Grafo G.d[v] é o vetor de distâncias de s até cada v.Admitindo-se a pior estimativa possível, o caminho infinito.π[v] identifica o vértice de onde se origina uma conexão até v de maneira a formar um caminho mínimo.
- 2º passo: temos que usar o conjunto Q, cujos vértices ainda não contém o custo do menor caminho d[v] determinado.
Q ← V[G]
- 3º passo: realizamos uma série de relaxamentos das arestas, de acordo com o código:
enquanto Q ≠ ø u ← extrair-mín(Q) //Q ← Q - {u} para cada v adjacente a u se d[v] > d[u] + peso(u, v) //relaxe (u, v) então d[v] ← d[u] + peso(u, v) π[v] ← upeso(u, v) é o peso da aresta que vai de u a v.
u e v são vértices quaisquer e s é o vértice inicial.ffdextrair-mín(Q), pode usar um heap de mínimo ou uma lista de vértices onde se extrai o elemento u com menor valor d[u].
No final do algoritmo teremos o menor caminho entre s e qualquer outro vértice de G. O algoritmo leva tempo O(m + n log n) caso seja usado um heap de Fibonacci, O(m log n) caso seja usado um heap binário e O(n²) caso seja usado um vetor para armazenar Q.
O algoritmo de Dijkstra é um exemplo de algoritmo guloso que gera a solução ótima em tempo polinomial.
Exemplo de código em c++
// Implementação do algoritmo de Dijkstra// Teste: http://br.spoj.com/problems/ENGARRAF/#include <iostream>#include <list>#include <queue>#define INFINITO 10000000using namespace std;class Grafo{private:int V; // número de vértices// ponteiro para um array contendo as listas de adjacênciaslist<pair<int, int> > * adj;public:// construtorGrafo(int V){this->V = V; // atribui o número de vértices/*cria as listas onde cada lista é uma lista de pairsonde cada pair é formado pelo vértice destino e o custo*/adj = new list<pair<int, int> >[V];}// adiciona uma aresta ao grafo de v1 à v2void addAresta(int v1, int v2, int custo){adj[v1].push_back(make_pair(v2, custo));}// algoritmo de Dijkstraint dijkstra(int orig, int dest){// vetor de distânciasint dist[V];/* vetor de visitados serve para caso o vértice já tenha sido expandido (visitado), não expandir mais*/int visitados[V];// fila de prioridades de pair (distancia, vértice)priority_queue < pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;// inicia o vetor de distâncias e visitadosfor(int i = 0; i < V; i++){dist[i] = INFINITO;visitados[i] = false;}// a distância de orig para orig é 0dist[orig] = 0;// insere na filapq.push(make_pair(dist[orig], orig));// loop do algoritmowhile(!pq.empty()){pair<int, int> p = pq.top(); // extrai o pair do topoint u = p.second; // obtém o vértice do pairpq.pop(); // remove da fila// verifica se o vértice não foi expandidoif(visitados[u] == false){// marca como visitadovisitados[u] = true;list<pair<int, int> >::iterator it;// percorre os vértices "v" adjacentes de "u"for(it = adj[u].begin(); it != adj[u].end(); it++){// obtém o vértice adjacente e o custo da arestaint v = it->first;int custo_aresta = it->second;// relaxamento (u, v)if(dist[v] > (dist[u] + custo_aresta)){// atualiza a distância de "v" e insere na filadist[v] = dist[u] + custo_aresta;pq.push(make_pair(dist[v], v));}}}}// retorna a distância mínima até o destinoreturn dist[dest];}};int main(int argc, char *argv[]){Grafo g(5);g.addAresta(0, 1, 4);g.addAresta(0, 2, 2);g.addAresta(0, 3, 5);g.addAresta(1, 4, 1);g.addAresta(2, 1, 1);g.addAresta(2, 3, 2);g.addAresta(2, 4, 1);g.addAresta(3, 4, 1);cout << g.dijkstra(0, 4) << endl;return 0;}Problemas relacionados
O algoritmo de Dijkstra não consegue encontrar o menor caminho em um grafo com pesos negativos. Para esse propósito, pode-se usar o algoritmo de Floyd-Warshall, que consegue descobrir a menor distância entre todos os pares de vértices de qualquer grafo sem ciclos com peso negativo em uma complexidade de tempo O(V³). Se o problema não exigir o cálculo da distância entre todos os pares de vértices pode-se aplicar o algoritmo de Bellman-Ford, com complexidade de tempo O(V*E).Em uma árvore, é possível encontrar a distância entre um vértice inicial e todos os outros vértices em tempo O(V+E), utilizando busca em profundidade (também conhecida como DFS). Em um grafo cujas arestas têm todas o mesmo peso, pode-se encontrar a distância entre um vértice inicial e todos os outros vértices, para um grafo qualquer, em O(V+E), utilizando busca em largura (também conhecida como BFS).O processo utilizado no algoritmo de Dijkstra é bastante similar ao processo usado no algoritmo de Prim. O propósito deste último, entretanto, é encontrar a árvore geradora mínima que conecta todos os nós de um grafo. O BFS pode ser visto como um caso especial do algoritmo de Dijkstra em grafos não dirigidos, onde a fila de prioridade assume o comportamento FIFO.
