Alguien me puede explicar el algoritmo de Floid para YA (Examen) XD

Que yo recuerde, floyd tenía por mision encontrar el camino mínimo entre nodos...por lo tanto por pasada se puede decir que actualiza la distancia mínima entre nodos determinados...la distancia entre la columna i de nodos y la fila j, entre columna i y fila j+1,etc...siento el valor de la columna (i,j) = 0, ya que es el mismo nodo.

La implementación era mediante una funcioncilla donde mediante una matriz de pesos inicial metida como parámetro valor,la función en su código comparaba los pesos entre las aristas y si encontraba un camino con peso menor lo actualizaba en una matriz auxiliar, si no en la auxiliar metía el peso inicial menor...teniendo finalmente en la auxiliar los nodos actualizados a sus caminos mínimos correspondientes.

Esto lo vi yo en diseño de algoritmos.El de dijkstra era parecido pero creo que sólo encontraba el camino mínimo para el vértice inicial con respecto a los demas.Este lo hace para todos con respecto a todos.

Como puedes observar en las transparencias es para grafos dirigidos, y la matriz te la presentan como una lista, camino de nodos 12, camino 11=0, camino 21, camino 31,etc...los infinitos los marca en aquellos caminos que no están inicialmente marcados con un valor, al no estar relacionados (dirigidos) con una flecha en esa dirección...pero el algoritmo mediante sucesivas pasadas acaba dándole un valor (pasadas son columnas en este caso) y a partir de cierta pasada actualiza el valor de infinito a un valor determinado, es decir al camino mínimo.

Fíjate en el nodo 13 , que parece ser el único para el que actualiza el valor a una mínimo...entre 13=3 mediante modo directo, el algoritmo detecta que yendo por camino 12,24,43=0...por lo tanto actualiza el camino mínimo 3 a 0.

Es muy general lo que te he dicho y hablo de memoria...busca por google a ver.

EDITO:actualiza bastantes caminos entre nodos pero en todos hace lo mismo que el 13...que es el último ejemplo.

Misión cumplicada!

gracias tio

¿Que tal el examen?

uff solo te digo que iba con la idea de que iba a ser un examen totalmente diferente, por suerte, con lo que sabía y lo que me pasaron allí mismo creo que aprobare.. xD

De puta madre entonces...me alegro tio

Un saludo