Algoritmo de Dijkstra

REFERÊNCIAS

Dijkstra, Edsger; Thomas J. Misa, Editor. (2010-08). "An Interview with Edsger W. Dijkstra"
CORMEN, Thomas H. LEISERSON Charles E. RIVEST, Ronald L. STEIN, Clifford. Algoritmos – teoria e prática. Campus, Rio de Janeiro, 2002.

GOLDBARG, Marco C. & LUNA Henrique P. L. Otimização combinatória e programação linear: modelos e algoritmos. Elsevier, Rio de Janeiro, 2005.

Algoritmo Comum
De modo geral pode-se dizer que:
“(...) o desenho de bons algoritmos para a determinação de elementos associados à conexidade em grafos está associado ao domínio de boas técnicas de busca em grafos.(...)”(GOLDBARG & LUNA, 2005, p. 230)
Assim, pode-se descrever uma busca em um grafo no seguinte algoritmo geral:
INÍCIO
Ler os dados de G, {grafo direcionado ou não}
Escolher e marcar um vértice inicial;
Enquanto existir N, j = 1, ..., n marcado e com uma aresta ( , ) não explorada efetuar Início
Escolher o vértice e explorar a aresta ( , ) {*condição variável em conformidade com o tipo de busca*}
Se é não marcado então marcar
Fim
FIM
Segundo Goldbarg e Luna, “o algoritmo geral descrito examina pelo menos duas vezes as arestas e os vértices de G, possuindo, portanto, complexidade O(nm)” (GOLDBARG &
LUNA, 2005, p. 231). Na medida que os critérios de escolha dos vértices podem exigir um esforço computacional maior, o tempo tende a aumentar com a complexidade, neste caso especifico o tempo de execução do algoritmo não é muito alto, dando ao mesmo um bom desempenho. Algoritmo de Dijkstra
O algoritmo de Dijkstra, segundo GOLDBARG & LUNA (2005), tem como objetivo obter o menor caminho entre um dado vértice fixo e todos os demais vértices do grafo (como por exemplo, saber a distância mínima entre uma loja e todos os seus clientes). Consiste basicamente em fazer uma visita por todos os nós do grafo, iniciando no nó fixo dado e encontrando sucessivamente o nó mais próximo, o segundo mais próximo, o terceiro