Presentación Algoritmo WarShall

Programacion y diseno de algoritmosAlgoritmo de Warshall

Aldo Guzman Ovalle

Universidad Politecnica de Victoria

13 de octubre de 2015

Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria

Definiciones basicasGrafos dirigidosLos grafos dirigidos son grafos con aristas orientadas en unadireccion. Ejemplo: E(G) = {e1, e2, . . . , e7} = {(A, D), (B, A),(B, A), (D, B), (B, C), (D, C), (B, B)}

Figura: Grafos dirigidos


Definiciones basicasP=(v1,v2,. . . vn): denominado camino, es la secuencia de verticesque se deben seguir para llegar del vertice v1(origen) al verticevn(destino). Ejemplo: A-E-F-H-I-J.

Figura: Camino


Definiciones basicasP=(v1,v2,. . . vn): se denomina camino simple, si los verticesexcepto el origen y el destino, son distintos. Ejemplo: El caminoA-E-F-D-B-A, es un camino simple, pero el caminoA-E-D-B-C-D-G no lo es.

Figura: Camino simple


Definiciones basicasLa matriz de adyacencia para G es una matriz A de dimensionnxn, de elementos booleanos, donde A[i,j] es verdadero si y solo siexiste un arco que vaya del vertice i al j.Con frecuencia se exhibiran matrices adyacencias con 1 paraverdadero y 0 para falso.

Figura: Matriz de adyacencia


Algoritmo de Warshall

Sea G un grafo dirigido con m vertices (v1,v2,. . . vm).Suponga quedesea encontrar la matriz de caminos P del grafo G. Warshallproporciono un algoritmo mucho mas eficiente que calcular laspotencias de la matriz de adyacencia A. Tal algoritmo se define enesta seccion, y un algoritmo semejante se utiliza para encontrar loscaminos mas cortos en G cuando G es ponderado.



Primero se definen las matrices booleanas mxm(P0,P1,. . .Pm),donde Pk [i , j ] denota la entrada ij de la matriz Pk :

Pk =

1 = si hay un camino simple de vi a vjque no use ningun otro vertice,excepto quizav1, v2, . . . , vk .0 = en otro caso.

(1)

Por ejemplo,Pk [i , j ] = 1 si hay un camino simple de vi a vj que no use ningunotro vertice, excepto quiza v1, v2, v3.



Observe que la primera matriz P0 = A es la matriz de adyacenciade G. Ademas, puesto que G solo tiene m vertices,la ultima matrizPm= P es la matriz de caminos de G. Warshall observo que Pk [i, j]= 1 puede pasar solo si ocurre uno de los dos casos siguientes:

1. Hay un camino simple de vi a vj que no usa ningun otrovertice, excepto quiza v1, v2, . . . , vk , ..., vk−1; por tanto,

Pk−1[i, j] = 1

2. Hay un camino simple de vi a vk y un camino simple de vk avj donde cada camino simple no usa ningun otro vertice,excepto quiza vk , ..., vk−1; por tanto,

Pk−11[i, k] =1 y Pk−1[k, j] = 1


Estos dos casos se representan como sigue:

1) vi →· · ·→vj2) vi → ··· → vk → ·· · vj

donde → · · ·→ denota parte de un camino simple que no usaningun otro vertice, excepto quiza v1, v2, ..., vk−1. En consecuencia,los elementos de Pk pueden obtenerse como sigue:

Pk [i, j] = Pk−1[i, j] ∨ (Pk−1[i, k] ∧ Pk−1[k, j])

donde se usan las operaciones logicas de ∧(AND) y ∨ (OR). Enotras palabras, cada entrada en la matriz Pk puede obtenersebuscando solo tres entradas en la matriz Pk−1. El algoritmo deWarshall se muestra en la figura.



Figura: Algoritmo de Warshall


Ejemplo del algoritmo de Warshall

G(V,E) Sea V={1,2,3,4 } y E{(1,2),(2,3),(3,4),(2,1) }

MR =

0 1 0 01 0 1 00 0 0 10 0 0 0



tij = 1

{Sij = 1Sik = 1 ∧Skj = 1

Datos:i=j=k=

MR =

0 1 0 01 0 1 00 0 0 10 0 0 0

W1 =



tij = 1

{Sij = 1Sik = 1 ∧Skj = 1

Datos:i=j=k=

W1 =

0 1 0 01 1 1 00 0 0 10 0 0 0

W2 =



tij = 1

{Sij = 1Sik = 1 ∧Skj = 1

Datos:i=j=k=

W2 =

1 1 1 01 1 1 00 0 0 10 0 0 0

W2 =



tij = 1

{Sij = 1Sik = 1 ∧Skj = 1

Datos:i=j=k=

W3 =

1 1 1 11 1 1 10 0 0 10 0 0 0

W4 =

1 1 1 11 1 1 10 0 0 10 0 0 0


Presentación Algoritmo WarShall

Technology

Transcript of Presentación Algoritmo WarShall