El algoritmo de Floyd intenta resolver el problema de encontrar el camino más corto entre todos los pares de nodos o vértices de un grafo. Esto es similar a construir una tabla con todas las distancias mínimas entre pares de ciudades de un mapa, indicando la ruta a seguir para ir de la primera ciudad a la segunda. Esto puede verse de la siguiente manera:

• Sea G= (V, A) un digrafo en el cual cada arco tiene asociado un costo no negativo. El problema es hallar para cualquier par de vértices (v, w) el camino más corto de v a w.
• G= (V, A), V= {1,...,n} y C[i, j] es el costo del arco que va de i a j.
• El algoritmo calcula la serie de matrices
• Ak[i, j] significa el costo del camino más corto que va de i a j y que no pasa por algún vértice mayor que k.
• El objetivo es calcular An[i, j]

Además de eso, se busca hallar también el camino más corto entre cada par de nodos, imprimiendo así en el programa no solo la matriz final sino también dichos caminos.

Solución al problema

La solución al problema se puede dar aplicando el algoritmo de Floyd para encontrar las distancias y caminos mínimos entre nodos. Una forma de implementar el algoritmo de Floyd en java es como se muestra en el siguiente fragmento de código. Se utilizó un enfoque dinámico, ya que se guardan valores en una matriz para luego reutilizarlos y no repetir operaciones.

 public String floyd(long[][] adyacencia)
   {
                int n=adyacencia.length;
                long D[][]=adyacencia;
 
                String enlaces[][]=new String [n][n];
                String[][] aux_enlaces=new String[n][n];

El método recibe una matriz, en este caso la matriz de adyacencia del grafo. Para calcular las distancias mínimas se crea una matriz D[][], la cual irá guardando los resultados que arroja el algoritmo de Floyd, y otra matriz que guardará los caminos mínimos llamada enlaces[][]. Los caminos mínimos se calculan, utilizando los diferentes k, que son guardados en la matriz enl_aux[][], y utilizada en el método enlaces(). El método enlaces, utiliza una llamada recursiva para recorrer la matriz de enlaces y arrojar el camino mínimo entre los nodos. Este resultado será guardado en la matriz enlaces[i][j].

Limitaciones

Las limitaciones que se encontraron con el algoritmo no son muchas, mejor dicho, no se encontraron, a excepción que cuando se va a resolver un grafo muy grande, éste no halla la respuesta porque se presenta un desborde de memoria, ya que debe iterar y almacenar demasiados valores.

Complejidad temporal

Este es el método principal, es decir, el que halla la solución del problema que se le plantee (la matriz de adyacencia):

Código fuente

Forma de compilar y ejecutar

Para poder compilar y ejecutar el programa debe tener instalado en su computador el jdk de java 1.5 o una actualización más reciente y además debe tener el path de su sistema configurado con el JDK.

Este programa está hecho en lenguaje Java, por lo que se puede compilar y ejecutar en cualquier IDE que tenga soporte JAVA; si usa Netbeans o Eclipse, debe primero crear un proyecto con el nombre que quiera, y crea tres clases con los correspondientes nombres usados en el código fuente y lógicamente pega dicho código en la clase. Si usa JCreator, puede bien sea, crear una única clase con el nombre de Aplicación y pega ahí todo el código fuente, o crea las tres clases con los nombres que son y pega el código fuente correspondiente en cada clase.

Tiempo empleado

El tiempo que nos tardo desarrollar el programa fue aproximadamente 3 días, el primer día desarrollando el algoritmo de solución, el segundo día desarrollando la interfaz grafica, y el tercero corrigiendo las excepciones que se pudieran presentar.

Pruebas

Esta es la matriz de adyacencia de un grafo que puede ser utilizada para probar la efectividad del algoritmo: La i representa infinito.

La respuesta es:

Los caminos mínimos entre nodos son:

De ( 1 a 2 ) = ( 1 , 2 )

De ( 1 a 3 ) = ( 1 , 2 , 4 , 3 )

De ( 1 a 4 ) = ( 1 , 2 , 4 )

De ( 2 a 1 ) = ( 2 , 4 , 1 )

De ( 2 a 3 ) = ( 2 , 4 , 3 )

De ( 2 a 4 ) = ( 2 , 4 )

De ( 3 a 1 ) = ( 3 , 1 )

De ( 3 a 2 ) = ( 3 , 1 , 2 )

De ( 3 a 4 ) = ( 3 , 4 )

De ( 4 a 1 ) = ( 4 , 1 )

De ( 4 a 2 ) = ( 4 , 1 , 2 )

De ( 4 a 3 ) = ( 4 , 3 )

Conclusiones

• Con las herramientas adecuadas y unos buenos fundamentos en programación, además de tener un conocimiento en grafos, se podría concluir que el algoritmo es fácil de implementar.
• Para hallar la solución óptima es mucho mejor usar el enfoque dinámico, ya que éste no repite operaciones y acelera un poco el proceso de solución.
• El algoritmo tiene una desventaja, debido a su enfoque dinámico, realiza un uso masivo de memoria, lo cual puede ser inconveniente.