All pairs Shortest paths – Algoritmo de la multiplicación de Matrices


All pairs Shortest paths – Algoritmo de la multiplicación de Matrices


Andrés David Chamorro Parejo



Definamos W=(wij), la matrix de pesos del Grafo G=(V,E) supongamos que G no tiene Ciclos negativos. El problema de encontrar los caminos mas cortos para cualquier par de vertices de el Grafo G tiene como salida (output) una matrix D = (dij) donde dij es el peso del camino mas corto desde el vértices i al j, en este articulo veremos un primer algoritmos que se asemeja mucho al del multiplicación de matrices.

Este algoritmo, para solucionar el problema, utiliza el paradigma de

programación dinámica.

  1. Caracterización de la subestructura optima, Consideremos que el camino p de i a j que tiene a lo mas m aristas. Como G no tiene Ciclos negativos m < ∞, si i=j entonces w(p)=0 y p no tiene aristas, si i ≠ j entonces podemos descomponer p en camino que va a un k predecesor de j en p, el camino de i a k es el camino mas corto de i a k ya que p lo es de i a j



    2.

  2. Sea lij (m) el mínimo peso de un camino de i a j que tiene a lo mas m aristas, cuando m=0 existe un camino si y solo si i=j.







    lij ={




    0 si


    i=j
    ∞
    si i ≠ j





    Para m ≥ 1 lijm es el mínimo entre lij m−1 y el peso de cualquier camino que tenga a lo mas m aristas obtenidos a observar todos los posibles predecesores k de j.




    l    ij(m)


    =min(l    ij(m−1),mink{lik (m−1) + wkj})




    =min    k{lik (m−1) + wkj}





    La ultima igualdad se tiene ya que w jj=0 para todo j.

    Como G no tiene Ciclos entonces el camino mas corto de i a j es simple tendrá en el peor de los casos n−1 aristas ósea.







    δ(ij)=l    ij n−1 = lij n = …


  3. Computemos la serie de matrices L (1),L (2),…,L (n−1) donde L (m)=(lijm), la matrix final L (n−1) contiene los pesos de los caminos mas cortos para cada par ij, observe que L (1)=W,

    el corazón del algoritmo es el siguiente procedimiento llamado:EXTEND-SHORTED-PATHS que tiene como entrada una matrix L (m−1) y W y retorna L (m)

    ESTEND-SHORTED-PATHS(L,W)

    1 N← rows[L]

    2 L′=(l′ij)

    3 for i ← 1 to n

    4 do for j ← 1 to n

    5 do l′ij ← ∞

    6 for k ← 1 to n

    7 do l′ij ← min(l′i,j,lij +w kj)

    8 return L′

    Este procedimiento se escribe sin superíndice para hacer la entrada y la salida independiente de m, es claro que este procedimiento pertenece al orden de O(n3) y si calculamos una a una las matrices L (m) nos tomara un tiempo de orden O(n4) lo que es muy costoso, veamos la relación que hay entre este procedimiento y el de multiplicación de matrices. Para calcular la matrix C=A ·B tendremos que calcular para todo par i,j=1,2,…,n.







    cij=

    n

    ∑

    k=1

    aik ·bkj

    Si hacemos la siguiente sustitución y definimos un semianillo.




    +


    → min


    ·


    +





    podemos redefinir el algoritmo de la multiplicación de matrices calculando cada elemento de la matrix producto como mink{lik(m−1) + wkj}) teniendo como la matrix identidad:







    L (0)=I =




    /0


    ∞


    …


    ∞\


    |∞


    0


    …


    ∞


    :


    :


    ···


    :


    ∞


    ∞


    …


    0







    Gracias a esto podemos calcular las “potencias” L (m) no de una en una sino en potencias de dos hasta m=2⎣lg (n−1)⎦ ya que δ(ij)=lij n−1 = lij n = …,y con esto disminuir el numero de iteraciones de O(n4) a O(n3lgn)



File translated from

TEX

by

TTHgold,

version 4.00.

On 07 Dec 2010, 03:43.

Mis Clases de Analisis de algoritmos

Mi primera impresión en el RUM es de fuerza, constancia, esfuerzo, o como dicen en una región de mi país, “Garra”. Son mis primeras clases totalmente en Ingles y al no ser muy bueno para los idiomas mi trabajo es triple con respecto a mis compañero…