ALGORITMO 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.

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.

CARACTERÍSTICAS DEL ALGORITMO DE WARSHALL

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

CÓMO 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)

Indicaría si hay camino DIRECTO

o pasando por V0 (Esto ya lo sabe P1)

O pasando por V1

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

O pasando por V2

Indicaría lo que ya sabe Pk-1

O pasando por Vk-1

Matriz de Caminos

Es una matriz cuadrada P, Que representa si hay o no camino Entre dos vértices Vi y Vj

ALGORITMO

Entre Vi y Vj puede haber caminoDirecto, cuando A[i][j] == 1, camino de long. 1 O pasando por otros vértices Si solo analizamos pasar por un Vk extra Cuando A[i][k] == 1 && A[k][j] == 1, Long. 2 Si Vk puede ser V1 o V2 o … Vn, realmente (A[i][1] && A[1][j]) || (A[i][2] && A[2][j]) || (A[i] [n] && A[3][n]) Que representa A * A, A2Nos indica solo si hay un camino de long. 2 entre Vi y Vj La matriz de caminos indicara si hay camino ya sea De long. 1 o de long. 2 o de long. 3 o de long. N, es decir:

WARSHALL MÁS EFICIENTE

El anterior algoritmo es poco eficiente, peor Cuando el grafo tiene muchos vértices Warshall propuso otro algoritmo mas eficiente Calcular una secuencia de matrices cuadradas De 0s(no hay camino) y 1s(hay camino) P0, P1, P2, P3… PN La diferencia entre Pk y Pk-1 Se basa añadir un vértice Vk-1 al análisis Para saber y a través de Vk-1 hay camino entre V1 y Vj