Please enable JavaScript.
Coggle requires JavaScript to display documents.
Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem - Coggle Diagram
Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem
Definição do problema
Problema dos caminhos mais curtos entre todos os pares
Encontrar a menor distância entre cada par de vértices em um grafo ponderado (direcionado ou não).
Matriz de Distâncias (D)
Elemento d 𝑖 𝑗 representa a distância do caminho mais curto do vértice i ao vértice j.
Aplicações
Redes de transporte
Pesquisa operacional
Redes de comunicação
Planejamento de movimentos em jogos de computador
Algoritmo de Floyd
Aplicável a grafos ponderados (direcionados ou não) sem ciclos de comprimento negativo
Séries de Matrizes 𝐷 ^ ( 𝑘 )
Matrizes 𝐷^(0),𝐷^(1),...,𝐷^(𝑛)
Cada matriz representa os comprimentos dos caminhos mais curtos com restrições específicas nos vértices intermediários.
Recorrência do Algoritmo
d ij ^(k) =min{d ij^ (k−1) ,d ik ^(k−1) +d kj ^(k−1) } para 𝑘 ≥ 1 k≥1
d ij ^(0) =w ij (peso inicial entre os vértices i e j)
Implementação em Pseudocódigo
ALGORITHM Floyd(W[1..n, 1..n])
//Implementa o algoritmo de Floyd para o problema dos caminhos mais curtos entre todos os pares
//Entrada: Matriz de pesos W de um grafo sem ciclos de comprimento negativo
//Saída: Matriz de distâncias dos comprimentos dos caminhos mais curtos
D ← W
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]}