Please enable JavaScript.
Coggle requires JavaScript to display documents.
IF672 (2020.1) - Levitin Aluno: Marcos André - Coggle Diagram
IF672 (2020.1) - Levitin Aluno: Marcos André
(8) Programação Dinâmica
(8.4) Algoritmos de Floyd e Warshall (308-311)
Algoritmo de Floyd para o problema dos menores caminhos para todos os pares
Grafo conectado de pesos
Distância de cada vértice para todos os outros vértices
Aplicações
Comunicações
Redes de transporte
Pesquisa de operações
Jogos de computador
Matriz distância
Guarda o tamanho dos menores caminhos
Gerada a partir do algoritmo de Floyd
Algoritmo de Floyd
Semelhante ao algoritmo de Warshall
Aplicado a grafos direcionados e não direcionados
Que não contêm um ciclo de tamanho negativo
Utiliza uma série de matrizes nxn com n vértices
Contém os tamanhos dos menores caminhos entre os vértices
D(0) = Matriz peso do grafo
D(n) = Matriz distância do grafo
Funcionamento: Varre os termos em busca da melhor opção
Eficiência = θ(|V|³)