O algoritmo de Floyd computa a matriz de distância de um grafo ponderado, com n vértices, em uma série de matrizes n x n: \( D^{(0)}, D^{(1)}, ..., D^{(k-1)}, D^{(k)}, ..., D^{(n)} \)
Cada uma dessas matrizes contém o comprimento dos menores caminhos com certas limitações, Sendo mais específico, se eu pegar o elemento \( d_{ij}^{(k)} \), o elemento da i-ésima linha e j-ésima coluna da matriz \( D^{(k)} \), é igual ao comprimento do menor caminho dentre todos os caminhos que partem do vértice i ao vértice j, com cada vértice intermediário (se houver algum) cuja numeração não é maior do que k
OBS: \( D^{(0)} \) é o começo da série, caso especial onde ele não admite vértices intermediários em seus caminhos, visto que k = 0
-
A última matriz da série, \( D^{(n)} \), contém o comprimento dos menores caminhos dentre todos os caminhos que passam por todos os n vértices intermediários. Esta é a matriz buscada, contendo todas as distâncias entre o vértice i e vértice j
Como no algoritmo de Warshall, os elementos de uma matriz \( D^{(k)} \) podem ser calculados a partir dos elementos da matriz \( D^{(k-1)} \). Como a matriz \( D^{(k)} \) possui os menores caminhos que passam pelos vértices enumerados não maiores do que k, temos dois subconjuntos distintos
-
-