sdssd

Algoritmo de Dijkstra 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.
Terminologia:
Um vértice é dito fechado caso o caminho mínimo da origem até ele já foi calculado; > Caso contrário, o vértice é considerado aberto; > F: Conjunto de vértices fechados; > A: Conjunto de vértices abertos; > N: Conjunto de vértices vizinhos ao vértice atual; > dt[i]: Vetor que armazena a distância entre o vértice de origem e o vértice i; > rot[i]: Vetor que armazena o índice do vértice anterior ao vértice i, no caminho cuja distância está armazenada em dt[i]; > \: subtração em conjuntos.

Algoritmo de Dijkstra

Exemplo de implementação:

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