Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dijkstra, Algoritmo de Floyd, A eficiência temporal do algoritmo depende…
Dijkstra
-
Tanto o algoritmo de Dijkstra quanto o algoritmo de Prim constroem uma subárvore de vértices que se expande selecionando o próximo vértice da priority queue.
A diferença é que o algoritmo de Dijkstra compara tamanho dos caminhos então há uma soma, enquanto o algoritmo de Prim não soma nada.
Algoritmo de Floyd
Dado um grafo conexo com peso, o Problema da Menor Distância entre Todos os Pares para encontrar as menores distâncias de cada vértice para todos os outros vértices.
-
O elemento d da linha i e da coluna j da matriz K é igual ao tamanho do menor caminho de todos os caminhos do vértice i até o vértice j com cada vértice intermediário, nenhum menor do que k.
-
-
Podemos modificar o algoritmo para obter também os menores caminhos, além da distância dos menores caminhos.
A eficiência temporal do algoritmo depende na estrutura de dados utilizada para implementar a priority_queue e para representar o grafo.
-
O( V² ) para grafos representados como matrizes de peso e uma priority_queue implementada como um array desordenado.
Para grafos representados por uma lista de adjacência e uma priority_queue como uma heap mínima, é O ( E log V )