Algoritmos y Estructura de Datos

Algortimo de Floyd

Historia

Robert W. Floyd (8 de junio de 1936 - 25 de septiembre de 2001) fue un prominente científico estadounidense en informática. Nacido en Nueva York, Floyd culminó el bachillerato a los 14 años. Se graduó en la Universidad de Chicago en 1953 a los 17 años y como Físico en 1958. Operador de computadoras en los años 60, publicó sus primeros artículos los cuales fueron de gran influencia y fue nombrado profesor asociado en la Universidad de Carnegie Mellon. Seis años más tarde fue nombrado profesor en la Universidad de Stanford. Entre sus contribuciones se encuentran el diseño y análisis de algoritmos eficientes para encontrar el camino más corto en un grafo y para el problema de reconocimiento de frases, pero probablemente su logro más importante fue el ser pionero, con su artículo de 1967 «Assigning Meanings to Programs», en el área de verificación de programas utilizando aserciones lógicas, donde aparece la importante noción de invariante, esencial para demostrar propiedades de programas iterativos. Floyd recibió el Premio Turing de la ACM en 1978 «por tener una clara influencia en las metodologías para la creación de software eficiente y confiable, y por haber contribuido a la fundación de las subáreas teoría del reconocimiento de frases, semántica de los lenguajes de programación, verificación automatizada de programas, síntesis automatizada de programas y análisis de algoritmos».

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.

Analisis

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 .

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

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

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

Implementacion en C++

                // Declaraciones en el archivo .h
                int cn; //cantidad de nodos
                vector< vector< int> > ady;

                // Devuelve una matriz con las distancias mínimas de cada nodo al resto de los vértices.
                vector< vector< int> > Grafo :: floydWarshall(){
                    vector< vector< int> > path = this->ady;

                    /* No tendría porqué ser necesario si ya hay ceros en las diagonales de ady */
                    for(int i = 0; i < cn; i++)
                        path[i][i] = 0;
                    
                    for(int k = 0; k < cn; k++)
                        for(int i = 0; i < cn; i++)
                            for(int j = 0; j < cn; j++){
                                int dt = path[i][k] + path[k][j];
                                if(path[i][j] > dt)
                                    path[i][j] = dt;
                            }
                    
                    return path;
                }
            

Link de apoyo

Historia de Robert W. Floyd

Explicacion del Algoritmo de Floyd

Algoritmo de Floyd-Warshall