ALGORITMO DE FLOYD

El algoritmo de Floyd descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución .

HISTORIA

Robert W. (Bob) Floyd nació en Nueva York el 8 de Junio de 1936 y murió el 25 septiembre 2001 en Stanford, California, fue un eminente científico de la computación.

VENTAJAS Encontrar el camino mas corto en una sola ejecución. Algoritmo que usa el método de programación dinámica.

El procedimiento principal y único para este proceso recorre la matriz tantas veces como nodos tenga el grafo.

[endif]--ANALISIS

[endif]--

1.Creamos dos matrices a la primera la denominaremos matriz ponderada y a la segunda matriz recorrido .

2. En la matriz Ponderada , empezamos a ingresar los valores de acuerdo al peso de cada arista , cuando no existe relación entre dos nodos su valor será infinito , la diagonal de la matriz siempre será nula .

![endif]--

3. Para llenar la tabla de recorrido se llena con el valor de su columna , en todas las columnas inicialmente.

![endif]--

Debemos evaluar las relaciones o la suma evaluamos las columnas de la A–E . Respecto a las Filas de A-E ), de la tabla de ponderaciones a la tabla de recorridos , para poder editar las dos tablas.

Solo podemos evaluar los campos que ya cuenten con un valor de peso en la arista , en el primer caso podemos evidenciar que solo podemos evaluar en la columna de A , el numero 6 , respecto a la Fila de A .

Para tener en cuenta el cambio la suma debe ser menor al valor de la ponderación

![endif]--

El cambio debemos realizarlo en la tabla de recorrido de igual forma y colocamos el nodo el cual estamos evaluando

![endif]--

[endif]--Seguimos con el recorrido en las columnas de B,C,D,E. realizando los respectivos cambios teniendo en cuenta que si la suma es menor al valor que ya esta en la casilla , lo reemplazamos de lo contrario se deja el mismo .