estructura de datos II: algoritmo warshall

ALGOTRITMO DE WARSHALL

El algoritmo de Warshall, 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.

Se basa en el hecho que “si existe un medio para ir del vértice u al v, y un medio de ir del vértice v al w entonces existe un medio de ir del vértice u al w”

El algoritmo de Warshall es un ejemplo de algoritmo booleano. A partir de una tabla inicial compuesta de 0`s (no hay correspondencia inicial en el grafo) y 1`s (hay una correspondencia, llamase “flecha”, entre nodos), obtiene una nueva matriz denominada “Matriz de Clausura Transitiva” en la que se muestran todas las posibles uniones entre nodos, directa o indirectamente. Es decir, si de “A” a “B” no hay una “flecha”, es posible que si haya de “A” a “C” y luego de “C” a “B”. Luego, este resultado se verá volcado en la matriz final.

Ejemplo
Para representar el algoritmo se parte de un grafo y a partir de este se realiza la matriz de adyacencia.


De a hacia b corresponde uno

De b a d

Asi con cada caso que correspondo lo Lo restante se marcan con 0

matriz de adyacencia 1

duplica la matriz matriz 1

si de “A” a “B” no hay una “flecha”, es posible que si haya de “A” a “C” y luego de “C” a “B”. Luego, este resultado se verá volcado en la matriz final.

Tomando en cuenta este enunciado y evaluando todas las posibles opciones nos damos cuenta que de b a b no hay un camino pero podemos llegar de b a d –a-b .

m1