Please enable JavaScript.

Coggle requires JavaScript to display documents.

Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem - Coggle Diagram

- - - - Não podem conter ciclos negativos
  - - - Próprios Caminhos mais curtos
  - - - Caminho mais curto
        
        Todos
        
        Pares de Vertice
- - - - D(0)
        
        Matriz de peso do gráfico
      - D(k−1)
        
        calcular elementos de cada matriz
        
        d (k) ij o elemento na i-ésima linha e na j-ésima coluna da matriz D (k).
        
        vi, uma lista de vértices intermediários, cada um numerado não superior a k, vj.
        
        d(k) iJ
        
        =
        
        1 more item...
      - D(k)
        
        Elemento ij
        
        é igual ao comprimento do caminho mais curto entre todos os caminhos do i-ésimo vértice ao j-ésimo vértice com cada vértice intermediário, se houver, numerado
        não superior a k.
      - D(n)
        
        Contém
        
        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 buscada.