algoritmo de floyd

• Dado un grafo dirigido con pesos, ¿cuales son las trayectorias de largos caminos ( es decir "distancias mas cortas") entre todos los pares de vertices?
• La matriz de distancias (matriz de pesos) sirve como punto de partida. Se realizan K iteraciones sobre la matriz buscando el camino mas corto.
• FLOYD calcula los caminos mas cortos entre todos los vertices de un grafo.

• Se basa en el siguiente principio
• Tomamos un vertice A
• Calculamos que sale mas varato, si 
• movernos entre B y C directamente o
• movernos entre B y C pasando por A

ALGORITMO:

void floyd (int A[ ] [ ])

{    

     for(i=0;i

     {

         

         A[ i ] [ i ] = 0; // hacer cero la diagonal principal 

     }

     

     for(k = 0;k// intermedio

     { 

           for (i=0; i// filas

           {

               for (j=0;j// columnas

               {

                   if(i!=j)

                   {

                          if ( (A[ i ] [ k ] + A [ k ] [ j ]) < A [ i ] [ j ] )

             // si nodo intermedio es menor que el actual cambia

                          {

                                  A [ i ] [ j ] = 

A[ i ] [ k ] + A [ k ] [ j ];

                               

                          }

                   }

               }

           }

     }

    

}

IMPLEMENTACION EN C


esta implementacion se trabajo con punteros. alguna consideraciones importantes

despto1=j+(i*nodos); esta instrucción esta dentro de 3 for anidados y lo que hace es dar la posición en
                                   notacion de punteros su similar en matrices seria la posición [ i ] [ j ].


despto2=k+(i*nodos);esta instrucción esta dentro de 3 for anidados y lo que hace es dar la posición en
                                   notacion de punteros su similar en matrices seria la posición [ i ] [ k ].

despto3=j+(k*nodos);esta instrucción esta dentro de 3 for anidados y lo que hace es dar la posición en
                                   notacion de punteros su similar en matrices seria la posición [ k ] [ j ].

nodos: es el tamaño de la matriz cuadrada (n x n) .... nodos x nodos (en nuestro caso)
                     
*(a+despto1) : es igual a que en una matriz tengamos a [i] [j]
*(a+despto2) : es igual a que en una matriz tengamos a [i] [k]
*(a+despto3) : es igual a que en una matriz tengamos a [k] [j]