Algoritmos y Estructura de Datos

Algortimo de Warshall

Historia

Stephen Warshall (15 noviembre 1935 a 11 diciembre 2006) nació en la ciudad de Nueva York . Durante su carrera, Warshall llevó a cabo la investigación y el desarrollo en los sistemas operativos , el diseño de compiladores , el diseño del lenguaje , y la investigación de operaciones . Warshall murió el 11 de diciembre de 2006, de cáncer en su casa de Gloucester, Massachusetts . Le sobreviven su esposa, Sarah Dunlap, y sus dos hijos, Andrew D. Warshall y Sophia VZ Warshall. Después de graduarse de Harvard, Warshall trabajó en ORO (Operation Research Office), un programa establecido por Johns Hopkins para realizar investigación y desarrollo para el Ejército de los Estados Unidos. En 1958, dejó ORO para ocupar un puesto en una empresa llamada Technical Operations, donde ayudó a construir un laboratorio de investigación y desarrollo para proyectos de software militar. En 1961, dejó Technical Operations para fundar Massachusetts Computer Associates. Posteriormente, esta empresa pasó a formar parte de Applied Data Research (ADR). Después de la fusión, Warshall formó parte de la junta directiva de ADR y administró una variedad de proyectos y organizaciones. Se retiró de ADR en 1982 y enseñó una clase semanal de hebreo bíblico en Temple Ahavat Achim en Gloucester, Massachusetts.

Cierre Transitivo

Cierre transitivo de una relación binaria es encontrar la relación binaria más pequeña, que siendo esta transitiva contiene al conjunto de pares de la relación binaria original.

Caracteristicas del algoritmo

Es una representación de algoritmo Booleano. Encuentra si posible un camino entre cada uno de los vértices de la gráfica dirigida. Es decir no presenta las distancia entre los vértices Se basa en un concepto llamado cerradura transitiva de la matriz de adyacencia El algoritmo de Warshall sirve para encontrar la cerradura transitiva de una relación binaria en el conjunto A. La clausura transitiva de una relación binaria es la relación binaria mas pequeña que siendo transitiva contenga el conjunto de pares de la relación binaria original.

Como funciona

Existe una matriz inicial P0

Indica si hay o no camino DIRECTO de Vi a Vj

La matriz que le sigue P1

Indicaría si hay o no camino DIRECTO (Esto ya lo sabe P0)

O pasando por V0 (añade este vértice al análisis)

P2

Indicaría si hay camino DIRECTO

o pasando por V0 (Esto ya lo sabe P1)

O pasando por V1

P3

Indicaría si hay camino DIRECTO o pasando por V0, o V1 (Lo sabe P2)

O pasando por V2

Pk

Indicaría lo que ya sabe Pk-1

O pasando por Vk-1

Implementacion en C++

                
                #include < iostream > 
                using namespace std;

                // defining the number of vertices
                #define nV 4

                #define INF 999

                void printMatrix(int matrix[][nV]);

                void floydWarshall(int graph[][nV]) {
                int matrix[nV][nV], i, j, k;

                for (i = 0; i < nV; i++)
                    for (j = 0; j < nV; j++)
                    matrix[i][j] = graph[i][j];

                for (k = 0; k < nV; k++) {
                    for (i = 0; i < nV; i++) {
                    for (j = 0; j < nV; j++) {
                        if (matrix[i][k] + matrix[k][j] < matrix[i][j])
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
                    }
                    }
                }
                printMatrix(matrix);
                }

                void printMatrix(int matrix[][nV]) {
                for (int i = 0; i < nV; i++) {
                    for (int j = 0; j < nV; j++) {
                    if (matrix[i][j] == INF)
                        printf("%4s", "INF");
                    else
                        printf("%4d", matrix[i][j]);
                    }
                    printf("\n");
                }
                }

                int main() {
                int graph[nV][nV] = {{0, 3, INF, 5},
                            {2, 0, INF, 4},
                            {INF, 1, 0, INF},
                            {INF, INF, 2, 0}};
                floydWarshall(graph);
                }
            

Link de apoyo

Warshall's Algorithm

Implementación de Algoritmo de Warshall en C++

Historia de Stephen Warshall