Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Floyd - Coggle Diagram
Algoritmo de Floyd
Problema do caminho mais curto de todos os pares
Dado um grafo, esse problema pede para encontrar o comprimento do caminho mais curto de cada vértice para todos os outros
Registra-se os comprimentos em uma matriz D (n x n), chamada de matriz distância
Elemento dij
Distância do vértice i para o vértice j (comprimento de i-ésimo vértice para o j-ésimo vértice)
Aplicável a grafos ponderados (direcionados e não direcionados) desde que não tenham ciclo de tamanho negativo
O algoritmo de Floyd calcula matriz de distância de um grafo ponderado de n vértices por meio de uma série de matrizes n x n
Cada uma dessas matrizes contém os comprimentos dos caminhos mais curtos com certas restrições no caminho
O elemento dij(k) é igual ao comprimento do caminho mais curto entre todos os caminhos do vértice i ao j com cada vértice intermediário numerado, não superior a k.
Começa com D(0)
Matriz de peso do grafo
Sem vértice intermediário
A última matriz da série D(n) contém os comprimentos dos caminhos mais curtos que pode usar n vértices como intermediários e não é diferente da matriz distância que está sendo buscada
Pode-se calcular todos os elementos de uma matriz D(k) a partir do predecessor imediato D(k-1)
Seja dij(k) o elemento de D(k)
Significa que é igual ao compriments do caminho mais curto do vértice i ao j com seus vértices intermediários numerados não superiores a K
Pode particionar esses caminhos em 2 subconjuntos
Os que não usam o k-ésimo vértice como intermediário e os que usam
Os caminhos do primeiro subconjunto tem seus vértices intermediários não superiores a k-1, sendo os mais curtos por definição dij (k-1)
Qual o comprimento do caminho mais curto no segundo subconjunto?
Se o grafo não tiver ciclo de comprimento negativo, pode usar os caminhos que usam Vk como vértice intermediário exatamente 1 vez
Caminhos tem a seguinte forma
Vi a Vk com cada vértice não superior a k-1 e caminho de Vk a Vj com cada vértice não superior a k-1
Eficiência Temporal
Cúbica
Sendo o comprimento do caminho mais curto de vi a vk entre os caminhos que usam vértices intermediários não maiores que k-1 igual a dkj(k-1), o comprimento do caminho mais curto entre os caminhos que usam o k-ésimo vértice é dik(k-1)+dkj(k-1)
O elemento da linha i e coluna j da matriz de distância atual D(k-1) é substituída pela soma dos elementos na mesma linha i e a coluna k e na mesma coluna j e linha k se e somente se a última soma for menor que o valor atual
Aplicações
Transporte
Pesquisa operacional
Comunicação
Planejamento de movimentos em jogos