Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem
Problema dos caminhos mais curtos de todos os pare
Dado um gráfico conectado ponderado (não direcionado ou direcionado), o problema dos caminhos mais curtos de todos os pares pede para encontrar as distâncias - ou seja, os comprimentos dos caminhos mais curtos - de cada vértice a todos os outros vértices.
É conveniente registrar os comprimentos dos caminhos mais curtos em uma matriz D(n × n)chamada matriz de distância:
o elemento d[i][j] na i-ésima linha e a j-ésima coluna desta matriz indica o comprimento do caminho mais curto do i-ésimo vértice até o j-ésimo vértice.
É aplicável a gráficos ponderados não direcionados e direcionados, desde que não contenham um ciclo de comprimento negativo. (A distância entre quaisquer dois vértices em tal ciclo pode ser arbitrariamente pequena repetindo o ciclo vezes suficientes.)
O algoritmo de Floyd calcula a matriz de distância de um gráfico ponderado com n vértices através de uma série de matrizes n × n:
D(0) ,..., D(k−1) ,D(k),..., D(n).
Cada uma dessas matrizes contém os comprimentos dos caminhos mais curtos com certas restrições nos caminhos considerados para a matriz em questão.
(i, j = 1, 2, . . . , n, k = 0, 1, ..., n),
d(k)[i][j] da matriz D(k)-> é igual ao comprimento do caminho mais curto entre todos os caminhos do i-ésimo vértice v(i) ao j-ésimo vértice v(j) com seus vértices intermediários numerados não superiores a k:
Em particular, a série começa com D(0), o que não permite nenhum vértice intermediário em seus caminhos; portanto, D(0) é simplesmente a matriz de pesos do gráfico.
A última matriz da série, D(n), contém os comprimentos dos caminhos mais curtos entre todos os caminhos que podem usar todos os n vértices como intermediários e, portanto, nada mais é do que a matriz de distância que está sendo procurada.
v(i), uma lista de vértices intermediários, cada um numerado não superior a k, v(j)
podemos calcular todos os elementos de cada matriz D(k) a partir do seu antecessor imediato D(k−1)
Podemos particionar todos esses caminhos em dois subconjuntos disjuntos: aqueles que não usam o vértice k-ésimo v(k) como intermediário e aqueles que o fazem.
não usam o vértice k-ésimo v(k) como intermediário
usam o vértice k-ésimo v(k) como intermediário
Como os caminhos do primeiro subconjunto têm seus vértices intermediários numerados não superiores a k − 1, o mais curto deles é, por definição de nossas matrizes, de comprimento d(k−1)[i][j] .
Se o gráfico não contém um ciclo de comprimento negativo, podemos limitar nossa atenção apenas aos caminhos no segundo subconjunto que usam o vértice v(k) como seu vértice intermediário exatamente uma vez
v(i), vértices numerados ≤ k − 1, v(k), vértices numerados ≤ k − 1, v(j) .
a eficiência temporal do algoritmo de Floyd é cúbica
Todos esses caminhos têm o seguinte formato:
cada um dos caminhos é composto de um caminho de v(i) a v(k) com cada vértice intermediário numerado não superior a k − 1 e um caminho de v(k) a v(j) com cada vértice intermediário com número não superior a k − 1.
o comprimento do caminho mais curto de v(i) a v(k)
entre os caminhos que usam vértices intermediários numerados não superiores a k − 1
d(k−1)[i][k]
entre os caminhos que usam vértices intermediários numerados não superiores a k − 1
d(k−1)[k][j]
o comprimento do caminho mais curto entre os caminhos que usam o vértice k-ésimo
d(k−1)[i][k] + d(k−1)[k][j] .
d(k)[i][j] = min{d(k−1)[i][j] , d(k−1)[i][k] + d(k−1)[k][j] } para k ≥ 1, d(0)[i][j] = w[i][j]
o elemento na linha i e na coluna j da matriz de distância atual D(k−1) é substituído pela soma dos elementos na mesma linha i e na coluna k ([i][k]) e na mesma coluna j e na linha k([k][j]) se e somente se a última soma for menor que seu valor atual.