4  ALGORITMO DE WARSHALL; CAMINOS MINIMOS

Sea G un grafo dirigido con m nodos , v₁,v₂,…,v_m. Suponga que queremos encontrar la matriz  de caminos p para el grafo G. Warshall dio un algoritmo para este propósito  que es mucho mas eficiente que calcular la potencias de la matriz de adyacencia A.

Algoritmo 8.1: (algoritmo de warshall). Un grafo dirigido G con M nodos esta en memoria
                        por su matriz adyacente A. este algoritmo encuentra la matriz de caminos
                        (booleana) P del grafo G.

1.     [inicializar P]. repetir para I,J=1,2,…M:
     Si A[I,J]=0, entonces: Hacer P[I,J]:=0;
     Si no: Hacer P[I,J]:=1
[Fin del bucle].

2.    [actualizar P]. repetir pasos 3y4 para K=1,2,..,M:

3.           repetir paso 4 para 1=1,2,…,M:

4.                  repetir para J=1,2,…,M:
                      hacer P[I,J]:=P[I,J] v (P[I,K] ^ P[K,J]).
              [Fin del bucle].
       [Fin del bucle del paso 3].
[Fin del bucle del paso 2].

5.    salir.

ALGORITMO DEL CAMINO MÍNIMO

Sea G un grafo dirigido con m nodos, v1,v2,…,vm. Suponga que G tiene peso; o sea, suponga que cada arista e de G tiene asignado un numero no negativo w(e) llamado peso o longitud  de la arista e. entonces G se puede mantener en memoria por su matriz de pesos w=(wij), definida como sigue:

               
                w(e) si hay una arista e de vi a vj
wij=
                0      si no hay arista de vi a vj

La matriz de caminos P nos dice si hay o no caminos entre los nodos. ahora queremos encontrar una matriz Q=(qij) que nos diga las longitudes de los caminos mínimos entre los nodos o, mas exactamente, una matriz Q=(qij), donde

                   qij=longitud del camino mínimo de vi a vj

Ahora describiremos una modificación del algoritmo de warshall que encuentra la matriz Q. definimos una secuencia de matrices Q0,Q1,…,Qm (análogas a las anteriores matrices p0,,P1,…,Pm) cuyas entradas vienen dadas por:

 QK[i,j]= la menor de las longitudes de los anteriores caminos de vi a vj o la suma de las longitudes de los anteriores caminos de vi a vk y vk a vj

Más exactamente,

QK[i,j]=MIN(Qk-1[i,j],     Qk-1[i,k]+Qk-1[k,j])

La matriz inicial Q0 es la misma que la matriz de pesos W excepto que cada 0 de W se reemplaza por 00 (o un numero muy, muy grande). la matriz final Qm será la matriz Q deseada.

Algoritmo 8.2: (algoritmo del camino mínimo). Un grafo con peso G de M nodos esta
            en memoria mediante su matriz de pesos W. este algoritmo encuentra la matriz Q
            tal que [I,J] es la longitud delo camino mínimo del nodo VI al nodo VJ. INFINITO
            es un número muy grande y MIN es la función del valor mínimo.

1.    [inicializar Q]. Repetir para I,J=1,2,…, M:
     Si W[I,J]=0, entonces: Hacer Q[I,J]:=INFINITO;
     Si no: Hacer Q[I,J]:=W[I,J].
[fin del bucle].

2.    [Actualizar Q]. Repetir pasos 3 y 4 para K=1,2,…, M:

3.           Repetir paso 4 para I=1,2,…, M:

4.                     Repetir para J=1,2,…, M:
                          Hacer Q[I,J]:=MIN(Q[I,J], Q[I,K]+Q[K,J]).
                  [Fin del bucle].
        [Fin del bucle del paso 3].
[Fin del bucle del paso 2].

5.    salir.