Algoritmo de dijkstra

RELATÓRIO DO ALGORITMO DE DIJKSTRA

O funcionamento do algoritmo
Definimos inicio e fim como os vértices onde o caminho deve começar e terminar, respectivamente.
Seja foi o conjunto dos vértices do grafo (ou digrafo) que já foram processados pelo algoritmo. Se um vértice pertencer a foi, então necessariamente seu custo mínimo já foi calculado.
Seja também custo[i] a menor distância de inicio até o vértice i.
Também definimos uma matriz de adjacências, grafo[u][v], indicando o custo da aresta de u a v.

No início do algoritmo determinamos foi = {inicio} e custo[inicio] = 0. A ideia é expandirmos o conjunto foi até englobar o vértice fim.
A cada passo atualizamos as distâncias custo[i] dos vértices que não estão no conjunto foi, ou seja, pegamos o último vértice inserido em foi, olhamos seus vizinhos, e verificamos se custo[vizinho] > custo[atual] + grafo[atual][vizinho]. Isto é, se o custo para chegar até vizinho pode ser reduzido caminhando de atual até vizinho. Se sim, então reduzimos custo[vizinho], atualizando seu valor para custo[vizinho] = custo[atual] + grafo[atual][vizinho]. Este passo muitas vezes é chamado de relaxamento.
Após esse passo, verificamos entre todos os vértices que não estão no conjunto foi e selecionamos o que tem menor custo[i]. Este vértice já está com a menor distância possível, ou seja, seu caminho de menor custo já foi determinado! Assim, incluímos esse vértice em foi, e voltamos para o processo de atualizar os vizinhos, repetindo o loop até que o vértice fim seja aquele a ser incluído em foi.
O algorítmo encontra-se anexado na pasta