Implementação em C++

Implementação em C/C++

• Implementação em C utilizando uma matriz de adjacências. Dependendo da quantidade limite de vértices (MAXV) pode se tornar ineficiente quanto ao uso de memória, sendo recomendado usar uma lista de adjacências

• Implementação em C++ utilizando uma lista de adjacências.

A implementação do algoritmo utilizando uma lista de adjacências é ligeiramente mais rápida que a implementação com uma matriz de adjacências para casos em que o número de arestas não se aproxima do pior caso (uma aresta ligando cada par de vértices); quando próximo ao pior caso, o desempenho é similar. Ambos possuem complexidade de tempo em torno de O(V²).

É possível obter uma solução em O(E + V log V) (custo amortizado), onde E é o número de arestas, utilizando um heap de fibonacci ou O(E log V) usando priority queue da STL de C++ para extrair o vértice não-visitado com menor distância. O heap simples, embora levemente mais lento que o heap de fibonacci, também pode ser usado para obter uma complexidade similar.