Algoritmo de Floy Paralelizado.

   El Algoritmo de Floyd resuelve el problema de encontrar la ruta más corta en todos los pares de nodos o vértices de un grafo, sin necesidad de definir un nodo o vértice inicial. Además de ello nos indica la distancia, y el recorrido a seguir. En esta oprtunidad  presentamos el algorimo de Floyd paralelizado.

   Antes de comenzar vamos hacer unas cuantas definiciones:

   Sea G = (V,E,w) un grafo con pesos, donde V = {v1, v2, v3, ..., vn } es el conjunto de vértices de G donde E es el conjunto de pares (vi,vj) cuyo peso viene dado por wij. Consideremos un conjunto de vértices { v1, v2, v3, ..., vk } , para cualquier para de vertices vi, vj considerar todos los caminos, tales que los vetices pertenecientes al camino pertenezcan a dicho conjunto para algún k <=n. Sea pk_ij el camino de peso minimo entre ellos y sea dk_ij el peso de dicho camino:

            * Si vk no pertenece al camino minimo entonces pk_ij = pk-1_ij.

           * Si vk pertenece al camino minimo entonces tenemos un camino minimo 
            de vi a vk y otro de vk a vj cada uno de esos caminos usa los vertices de 
            { v1,...,vk}.

Nota:
   siendo más exigentes el camino de vk a vj excluye al vertice vi el camino de vi a vk excluye al vertice vj siendo aún más exigentes el camino vi a vk se intersectan con el camino de de vk a vj en un solo vertice.

Con ello podemos plantear la siguiente ecuación:

Algoritmo secuencial:

 

procedure FLOY_ALL_PAIRS_SP(A)

  D0 = A;

  for k:=1 to n do

      for i:=1 to n do

          for j:=1 to n do

              dk_ij = min( dk-1_ij , dk-1_ik + dk-1_kj );

end FLOY_ALL_PAIRS_SP

Algoritmo de Floyd usando una malla de  2 dimensiones

Descripción del algoritmo:

Se particiona la matriz de adyacencia del grafo G en bloques que dos dimensiones asignándoles una submatriz de n/sqrt(p) *n/sqrt(p) a cada procesador. Al proceso que se encuentra en la i-th fila y j-th columna le representaremos por Pij. Durante la k-ésima iteración cada proceso necesita ciertos segmento de la columna k y de la fila k. Por ejemplo si queremos calcular dk_lr necesitamos dk-1_lk y dk-1_kr como se puede apreciar en la figura.

procedure FLOYD_2D_BLOCK( D0 )

begin

    for k:=1 to n do

    begin

        each process Pi,j that has a segment of the k_th row of D_k-1;

        broadcast it to the P*,j processes;

        each process Pi,j that has a segment of the k_th column of D_k-1;

        broadcast it to the to the Pi,* processes;

        each process wait to receive the neede segments;

        each process Pi,j computes its part of the D_k matrix;

    end

end FLOY_2D_BLOCK

   
Algoritmo Paralelo Bidimensional:

Lecturas :

"Floyd uno los pioneros de las Ciencias de la Computación" , reporte de la Universidad de Standford 2001