Please enable JavaScript.
Coggle requires JavaScript to display documents.
Floyd's Algorithm - Coggle Diagram
Floyd's Algorithm
aplicações práticas
comunicações
redes de transporte
pesquisa operacional
pré calculo de distâncias em jogos
all pairs shortest-paths problem
achar a menor distância para todos os pares de vértices do grafo
observações
o grafo não pode ter ciclos negativos
o algoritmo também acha o menor caminho de um vértice para ele mesmo
se não há arestas entre dois vértices a distância é dita infinita
distance matrix
distância entre os vértices
OBS: D(0) = W
passo a passo
usa um conjunto de matrizes
inicia com D(0)
matriz sem vértices intermediários
cada vértice correspode a uma número k
para cada posição "Dij" atualizamos a distância considerando se o vértice "k" é intermediário ou não
procura-se a distância mínima usando o vértice k como intermediário e sem usar k
atualiza a matriz com o mínimo
weight matrix
peso das arestas
time efficiency
O(n^3) / cúbica