Post on 23-Feb-2017
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
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
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
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
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
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
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
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
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.
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
Algoritmo de Warshall
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.
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
Algoritmo de Warshall
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
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
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.
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
Algoritmo de Warshall
Figura: Algoritmo de Warshall
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
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
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
Ejemplo del algoritmo de Warshall
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 =
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
Ejemplo del algoritmo de Warshall
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 =
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
Ejemplo del algoritmo de Warshall
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 =
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria
Ejemplo del algoritmo de Warshall
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
Programacion y diseno de algoritmos Algoritmo de Warshall Universidad Politecnica de Victoria