Se realizó el quiz #9

Algoritmo de Floyd

A diferencia de Dijkstra este algoritmo es de tipo dinámico, y se logra en una sola iteración, lo cual no se podía hacer con Dijkstra (el cual tenía que hacer una iteración por arista). Este algoritmo representa al grafo como una matriz D0 con pesos. Si un arco no existe, se pone un infinito. La diagonal de la matriz debe ser igual a 0. Luego se genera, junto a D0 una matriz Q0. La diagonal también debe ser formada por ceros. Si hay infinitos en D0, se colocan 0 en la misma posición en Q0. En los casos (i,j) donde sí hay comunicación, se pone el número de la fila de ese momento. Luego, se van generando matrices D1, D2, D3 al igual que Q1, Q2, Q3, al mismo tiempo, hasta la N cantidad de iteraciones, esto para calcular los valores que corresponden a cada posición de la matriz.