Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Floyd - Coggle Diagram
Algoritmo de Floyd
-
O algoritmo começa com a matriz de pesos(D0), e então vai se modificando até chegar na Dn
Para cada Dk é verificada se o menor caminho entre dois vértice é o caminho atual (que caso não tenha é "setado" como infinito) ou o caminho atual passando pelo vértice k ( se possível)
Min(dist(i,j), dist(i,k)+dist(k,j))
-
É possível separar os caminhos em dois conjuntos, os que passam pelo vértice k e os que não passam
-
-
Esse algoritmo utiliza "matrizes" para armazenar as distancias, ("marizes" pois sobrescrevemos a mesma matriz n vezes, e cada vez que sobrescrevemos chamamos a "nova matriz" de Dk)
Ao fim do processo temos a matriz de distancias, que uma matriz n x n, onde d[ i ][ j ] é a menor distância entre i e j
-