Algoritmo de Dijkstra para cálculo do Caminho de Custo Mínimo

O Algoritmo de Dijkstra (E.W. Dijkstra) é um dos algoritmos que calcula o caminho de custo mínimo entre vértices de um grafo. Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do grafo. Ele é bastante simples e com um bom nível de performance. Ele não garante, contudo, a exatidão da solução caso haja a presença de arcos com valores negativos.

Este algoritmo parte de uma estimativa inicial para o custo mínimo e vai sucessivamente ajustando esta estimativa. Ele considera que um vértice estará fechado quando já tiver sido obtido um caminho de custo mínimo do vértice tomado como raiz da busca até ele. Caso contrário ele dito estar aberto.

Algoritmo: Seja G(V,A) um grafo orientado e s um vértice de G:

1. Atribua valor zero à estimativa do custo mínimo do vértice s (a raiz da busca) e infinito às demais estimativas;
2. Atribua um valor qualquer aos precedentes (o precedente de um vértice t é o vértice que precede t no caminho de custo mínimo de s para t);
3. Enquanto houver vértice aberto:
   • seja k um vértice ainda aberto cuja estimativa seja a menor dentre todos os vértices abertos;
   • feche o vértice k
   • Para todo vértice j ainda aberto que seja sucessor de k faça:
     • some a estimativa do vértice k com o custo do arco que une k a j;
     • caso esta soma seja melhor que a estimativa anterior para o vértice j, substitua-a e anote k como precedente de j.

A seqüência de diagramas^*  ilustra o funcionamento do Algoritmo de Dijkstra.

Inicialmente todos os nodos tem um custo infinito, exceto s (a raiz da busca) que tem valor 0: vértices s u v x y estimativas 0 ¥ ¥ ¥ ¥ precedentes - - - - -
selecione s (vértice aberto de estimativa mínima) feche s recalcule as estimativas de u e x vértices s u v x y estimativas 0 10 ¥ 5 ¥ precedentes s s - s -
selecione x (vértice aberto de estimativa mínima) feche x recalcule as estimativas de u,v e y vértices s u v x y estimativas 0 8 14 5 7 precedentes s x x s x
selecione y (vértice aberto de estimativa mínima) feche y recalcule a estimativa de v vértices s u v x y estimativas 0 8 13 5 7 precedentes s x y s x
selecione u (vértice aberto de estimativa mínima) feche u recalcule a estimativa de v vértices s u v x y estimativas 0 8 9 5 7 precedentes s x u s x
selecione v (vértice aberto de estimativa mínima) feche v vértices s u v x y estimativas 0 8 9 5 7 precedentes s x u s x

Quando todos os vértices tiverem sido fechados, os valores obtidos serão os custos mínimos dos caminhos que partem do vértice tomado como raiz da busca até os demais vértices do grafo. O caminho propriamente dito é obtido a partir dos vértices chamados acima de precedentes.

Para exemplificar, considere o caminho de custo mínimo que vai de s até v, cujo custo mínimo é 9. O vértice precendente de v na última das tabelas acima é u. Sendo assim, o caminho é:

s ® ... ® u ® v

Por sua vez, o precedente de u é x. Portanto, o caminho é:

s ® ... ® x ® u ® v

Por último, o precedente de x é o próprio vértice s. Logo, o caminho de custo mínimo é:

s ® x ® u ® v

Como apresentado o algoritmo de Dijkstra computa apenas um único caminho de custo mínimo entre um dado par de vértices. Para se obter todos os caminhos de custo mínimo entre dois vértices é necessário modificar a forma de anotação dos precedentes. A modificação no passo 3 indicada a seguir é suficiente para permitir o cômputo de todos os caminhos por um processo similar ao descrito acima.

...
Para todo vértice j ainda aberto que seja sucessor de k faça:

• some a estimativa do vértice k com o custo do arco que une k a j;
• caso esta soma seja melhor que a estimativa anterior para o vértice j, substitua-a e anote k como precedente único de j;
• caso esta soma seja igual à estimativa anterior para o vértice j, adicione k ao conjunto dos precedentes de j;

Supondo que o peso do arco (y,v) no grafo acima fosse 2, haveriam dois caminhos de custo mínimo do vértice s para v. Esta duplicidade resulta em dois precedentes para o vértice v:

Sendo assim, os dois caminhos são dados por: (s ® ... ® u ® v) e (s ® ... ® y ® v). Seguindo as precedências para u e y nestes dois casos obtemos os dois caminhos: (s ® x ® u ® v) e (s ® x ® y ® v).