Análise de Complexidade e Empírica do algoritmo de Dijkstra

O Algoritmo
O algoritmo utilizado na geração das tabelas de roteamento foi o algoritmo de Dijkstra, um dos mais conhecidos para o cálculo de caminho de custo mínimo entre vértices de um grafo.
Funcionamento do algoritmo
1) Define-se inicialmente o nó de origem (raiz), e inclui-se este nó em um vetor auxiliar. Atribui-se zero a sua distância. Todos os outros nós tem suas distâncias inicializadas com um valor bastante grande ("infinito"). Veja o exemplo a seguir: (*Perm é o vetor auxiliar e *Path é o vértice precedente no caminho)
2) A partir do vértice inicial consulta-se os vértices adjacentes a ele, que no grafo são u e x. Para todos os vértices adjacentes, que chamaremos z, calcula-se: Se dist[z] > dist[s] + peso(s, z) dist[z] = dist[s] + peso(s, z) path[z] = s Fim Se

3) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor distância. Neste caso é o vértice x, pois dist[x] = 5.

4) Inclui-se x em PERM e a partir de x consulta-se os vértices adjacentes a ele que não estão em PERM, que no grafo G são u, v e y. Então calcula-se a distância dos vértices adjacentes:

O processo é repetido até que todos os vértices estejam em PERM e seus precedentes estejam definidos. Resultando em:

PS: O algoritmo calcula a melhor rota de todos os vértices para um vértice específico. Para se ter a melhor rota de todos os vértices para todos os demais será necessário executar o algoritmo N vezes.
Complexidade do algoritmo for(int i=0;i O(n) conj[i].distancia=100000; // O(1) conj[i].anterior=null; // O(1) } vet = new Rota[numvert]; // O(1) int calc = 0; // O(1) raiz.distancia=0; // O(1) raiz.anterior = raiz;