O algoritmo de Dijkstra para calcular o caminho do custo mínimo

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:

o seja k um vértice ainda aberto cuja estimativa seja a menor dentre todos os vértices abertos;

o feche o vértice k

o 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    

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    

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    

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    

precedentes s x u s x

• selecione v (vértice aberto