Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Floyd-Warshall - Coggle Diagram
Algoritmo de Floyd-Warshall
1. Objetivo
Encontrar os menores caminhos entre todos os pares de vértices.
Resolve o problema do caminho mínimo global.
Funciona em grafos ponderados (positivos ou negativos, sem ciclos negativos).
2. Ideia Central
Baseia-se em programação dinâmica.
Usa uma matriz de distâncias D[ i ][ j ].
A cada iteração, verifica se passar por um vértice intermediário k melhora o caminho entre i e j.
Atualiza a distância conforme:
→ D[ i ] [ j ] = min(D[ i ] [ j ], D[ i ][ k ] + D[ k ][ j ])
3. Passos do Algoritmo
Inicializar D[ i ][ j ] com os pesos das arestas.
Para cada vértice k:
Para cada par (i, j) de vértices:
Atualizar D[ i ][ j ] se o caminho via k for menor.
Ao final, D contém as menores distâncias entre todos os pares.
4. Características
Complexidade: O(n³).
Aceita pesos negativos, desde que não haja ciclos negativos.
Produz uma matriz completa de menores caminhos.
Fácil de implementar (três laços aninhados).
5. Aplicações
Planejamento de rotas em redes grandes.
Análise de conectividade entre todos os nós.
Otimização global em sistemas de transporte, comunicações ou logística.