Please enable JavaScript.
Coggle requires JavaScript to display documents.
ALGORITMO DE FLOYD-WARSHALL - Coggle Diagram
ALGORITMO DE FLOYD-WARSHALL
Encontra o tamanho do menor caminho entre dois vértices quaisquer
All-pairs-shortest paths
Pode ser usado em grafos de peso com custos negativos, mas sem ciclos negativos
Eficiência Cúbica
Funcionamento
MATRIZ DE DISTÂNCIAS
Conjunto de n+1 matrizes n x n (ou uma única matriz nxn se for possível modificá-la
A k-ésima matriz armazena em cada posição Aij o tamanho do menor caminho entre os vértices i e j que passem somente por vértices de índice menor ou igual a K
A matriz K(0) armazena apenas os pesos das arestas
A matriz K(n) armazena o menor caminho definitivo entre cada par de vértice
Quando não há nenhum caminho entre i e j que cumpra os requerimentos, o valor armazenado na matriz é infinito
A cada iteração de K, a matriz reescreve o tamanho dos caminhos apenas se tiver sido encontrado um caminho menor do que o já armazenado
min{ D[i, j ], D[i, k]+D[k, j ] }
O algoritmo necessita de uma classificação de ordem entre os vértices, de forma que seja possível associar um índice K a um dos vértices e classificar um conjunto de vértices cujo índice não ultrapasse K - 1
Iterações de K comparam o menor caminho entre i e j passando apenas por vértices até (K-1) e apenas passando por vértices até K
K
d kj (k-1)
j
d ik (k-1)
i
d ij (k-1)
Pseudo-código
for
k ← 1 to n
do
for
i ← 1 to n
do
for
j ← 1 to n
do
D[i, j ] ← min{D[i, j ], D[i, k] + D[k, j ]}
return
D
D[0,1..n-1] = Matriz rescritível de distâncias.
k = Iteração que reescreve a matriz baseado em caminhos que passam por vértices iguais ou menores que k
i = Iteração que percorre linhas da matriz
j = Iteração que percorre colunas da matriz