FloydWarshall

Prévia do material em texto

Algoritmo de Floyd-Warshall
Considera grafos valorados (dirigidos ou não).
Calcula a menor distância entre todos os pares de vértices.
O algoritmo é bastante simples e utiliza a representação por matriz de adjacências.
Utiliza a técnica de programação dinâmica. A tabela auxiliar é a própria matriz de adjacências.
Considerando um grafo valorado de n vértices v1, v2, ..., vn. O algoritmo consiste de dois passos básicos:
Se (vi, vj) é uma aresta, fazer d(i, j) o peso dessa aresta. Caso contrário, d(i, j) = ∞ .
Para k = 1 até n,
Para i, j = 1 até n, fazer 
d(i, j) = min{d(i, j), d(i, k) + d(k,j)}
O valor final d(1, j) é a menor distância entre vi e vj.
O algoritmo de Floyd-Warshall é muito eficiente em termos de espaço requerido para armazenamento. A implementação pode utilizar a própria matriz de adjacências para atualizar as distâncias.