Please enable JavaScript.
Coggle requires JavaScript to display documents.
M12 - Coggle Diagram
M12
Definição
Algoritmo de caminho mais curto em grafos ponderados.
Encontra o caminho mínimo de um nó origem a todos os outros nós no grafo.
-
Exploração
Para o nó atual, considere todos os seus vizinhos ainda não visitados.
-
Se essa distância calculada for menor que a distância registrada, atualize a distância do vizinho.
Atualização
-
Se todos os nós foram visitados, termine.
Se não, escolha o nó não visitado com a menor distância registrada como o novo nó atual e repita o processo.
Características
-
Tempo de execução: O(V^2) para grafos densos, melhorado para O(E + V log V) com a utilização de uma fila de prioridade binária (heap).
-
-
-