Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmo de Floyd - Coggle Diagram

- - - - \(D^{(k)}\) indica a matriz distância entre qualquer par de vértices com cada vértice intermediário numerado até k
  - - - Um que não utiliza o vértice k-ésimo vértice \(v_{k}\) como intermediário e o que utiliza
        
        Como os caminhos da 1ª partição tem, como intermediários, vértices até \(k-1\), o menor dos caminhos é \(d^{(k-1)}_{ij}\)
        
        Em que \(d^{(k-1)}_{ij}\) significa a distância do vértice na linha \(i\) ao vértice na coluna \(j\) com vértices numerados até \(k-1\)
        
        Na 2ª partição, o comprimento do menor caminho entre aqueles que usam o k-ésimo vértice é \(d^{(k-1)}_{ik}+d^{(k-1)}_{kj}\)
        
        Em que \(d^{(k-1)}_{ik}\) é a distância do vértice na linha \(i\) ao vértice na coluna \(k\) com vértices intermediários numerados até \(k-1\)
        
        E \(d^{(k-1)}_{kj}\) possui raciocínio análogo, mas com o vértice da linha \(k\) e o da coluna \(j\)
        
        A distância entre o vértice da linha \(i\) e o vértice da coluna \(j\) na matriz \(D^{(k)}\) será o mínimo entre as distâncias das duas partições
        
        \(d_{ij}^{\left(k\right)}=\min(d^{k-1}_{ij}, d^{(k-1)}_{ik}+d^{(k-1)}_{kj})\)