Please enable JavaScript.

Coggle requires JavaScript to display documents.

Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem, v(i), vértices…

- - - - 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:
        
        v(i), uma lista de vértices intermediários, cada um numerado não superior a k, v(j)
        
        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.
        
        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
        
        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
        
        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] .
      - podemos calcular todos os elementos de cada matriz D(k) a partir do seu antecessor imediato D(k−1)
      - 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.