Programación en Java/Apéndices/Implementación del algoritmo de Floyd en Java
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
editarLa 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[adyacencia.length][adyacencia.length];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
enlaces[i][j]="";
aux_enlaces[i][j]="";
}
}
String enl_rec="";
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
float aux=D[i][j];
float aux2=D[i][k];
float aux3=D[k][j];
float aux4=aux2+aux3;
float res=Math.min(aux,aux4);
if(aux!=aux4)
{
if(res==aux4)
{
enl_rec="";
aux_enlaces[i][j]=k+"";
enlaces[i][j]=enlaces(i,k,aux_enlaces,enl_rec)+(k+1);
}
}
D[i][j]=(long) res;
}
}
}
String cadena="";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cadena+=D[i][j]+" ";
}
cadena+="\n";
}
String enlacesres="";
for (int i = 0; i <n; i++) {
for (int j = 0; j < n; j++) {
if(i!=j)
{
if(enlaces[i][j].equals("")==true)
{
enlacesres+=" De ( "+(i+1)+" a "+(j+1)+" ) = "+"( "+(i+1)+" , "+(j+1)+" )"+"\n";
}
else
enlacesres+=" De ( "+(i+1)+" a "+(j+1)+" ) = ( "+(i+1)+" , "+enlaces[i][j]+" , "+(j+1)+")\n";
}
}
}
return "las distancias minimas entre nodos son: \n"+cadena+"\nlos caminos minimos entre nodosson:\n"+enlacesres;
}
public String enlaces(int i,int k,String[][] aux_enlaces,String enl_rec)
{
if(aux_enlaces[i][k].equals("")==true)
{
return "";
}
else
{
enl_rec+=enlaces(i,Integer.parseInt(aux_enlaces[i][k].toString()),aux_enlaces,enl_rec)+(Integer.parseInt(aux_enlaces[i][k].toString())+1)+" , ";
return enl_rec;
}
}
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 el 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
editarLas 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
editarEste es el método principal, es decir, el que halla la solución del problema que se le plantee (la matriz de adyacencia):
| Instrucción | Tiempo |
|---|---|
| long[][] adyacencia | 1 |
| int n=adyacencia.length | 1 |
| long D[][]=adyacencia | 1 |
| String enlaces[][]=new String [n][n] | 1 |
| String[][] aux_enlaces=new String[adyacencia.length][adyacencia.length] | 1 |
| (1)for concatenados | |
| String enl_rec="" | 1 |
| (2)for concatenados | |
| enlaces (int i, int k, String[][] aux_enlaces,String enl_rec) | 1 |
| if(aux_enlaces[i][k].equals("")==true) | 1 |
| return " | 1 |
| enl_rec+=enlaces (i, Integer.parseInt(aux_enlaces[i][k].toString()),aux_enlaces,enl_rec)+(Integer.parseInt(aux_enlaces[i][k].toString())+1)+" , " | an+b |
| T (n)= y |
Código fuente
editarClase Aplicación
editar import javax.swing.UIManager;
import javax.swing.UnsupportedLookAndFeelException;
public class Aplicacion
{
public static void main(String args[])
{
try
{
UIManager.setLookAndFeel("com.sun.java.swing.plaf.windows.WindowsLookAndFeel");
} catch (ClassNotFoundException e)
{
e.printStackTrace();
} catch (InstantiationException e)
{
e.printStackTrace();
} catch (IllegalAccessException e)
{
e.printStackTrace();
} catch (UnsupportedLookAndFeelException e)
{
e.printStackTrace();
}
Ventana miVentana;
Logica logica;
miVentana=new Ventana();
logica=new Logica();
}
}
Clase Lógica
editar import javax.swing.JOptionPane;
public class Logica
{
public void setVentana(Ventana miVentana){}
public String floyd(long[][] adyacencia)
{
int n=adyacencia.length;
long D[][]=adyacencia;
String enlaces[][]=new String [n][n];
String[][] aux_enlaces=new String[adyacencia.length][adyacencia.length];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
enlaces[i][j]="";
aux_enlaces[i][j]="";
}
}
String enl_rec="";
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
float aux=D[i][j];
float aux2=D[i][k];
float aux3=D[k][j];
float aux4=aux2+aux3;
float res=Math.min(aux,aux4);
if(aux!=aux4)
{
if(res==aux4)
{
enl_rec="";
aux_enlaces[i][j]=k+"";
enlaces[i][j]=enlaces(i,k,aux_enlaces,enl_rec)+(k+1);
}
}
D[i][j]=(long) res;
}
}
}
String cadena="";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cadena+=D[i][j]+" ";
}
cadena+="\n";
}
String enlacesres="";
for (int i = 0; i <n; i++) {
for (int j = 0; j < n; j++) {
if(i!=j)
{
if(enlaces[i][j].equals("")==true)
{
enlacesres+=" De ( "+(i+1)+" a "+(j+1)+" ) = "+"( "+(i+1)+" , "+(j+1)+" )"+"\n";
}
else
enlacesres+=" De ( "+(i+1)+" a "+(j+1)+" ) = ( "+(i+1)+" , "+enlaces[i][j]+" , "+(j+1)+")\n";
}
}
}
return "las distancias minimas entre nodos son: \n"+cadena+"\nlos caminos minimos entre nodosson:\n"+enlacesres;
}
public String enlaces(int i,int k,String[][] aux_enlaces,String enl_rec)
{
if(aux_enlaces[i][k].equals("")==true)
{
return "";
}
else
{
enl_rec+=enlaces(i,Integer.parseInt(aux_enlaces[i][k].toString()),aux_enlaces,enl_rec)+(Integer.parseInt(aux_enlaces[i][k].toString())+1)+" , ";
return enl_rec;
}
}
}
Clase Ventana
editar import java.awt.Container;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
import javax.swing.JOptionPane;
import javax.swing.JTextField;
public class Ventana extends JFrame implements ActionListener
{
int a=ingreso("Ingrese el numero de nodos");
Container contenedor;
JLabel[] etiqueta1;
JLabel[] etiqueta2;
JTextField[][] matriz;
JTextArea mensaje;
JTextArea mayor;
JScrollPane scrollpane;
JScrollPane scrollpanemayor;
JButton aceptar;
public Ventana()
{
matriz=new JTextField[a][a];
etiqueta1=new JLabel[a];
etiqueta2=new JLabel[a];
contenedor=getContentPane();
contenedor.setLayout(null);
mayor=new JTextArea();
scrollpanemayor=new JScrollPane(mayor);
scrollpanemayor.setBounds(0,0,600,474);
scrollpanemayor.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS);
scrollpanemayor.setHorizontalScrollBarPolicy(JScrollPane.HORIZONTAL_SCROLLBAR_ALWAYS);
for(int i=0;i<a;i++)
{
etiqueta1[i]=new JLabel(""+(i+1));
etiqueta2[i]=new JLabel(""+(i+1));
etiqueta1[i].setBounds((int) ((i+2.4)*25),25,25,25);
etiqueta2[i].setBounds(21,(i+2)*25,25,25);
mayor.add(etiqueta1[i]);
mayor.add(etiqueta2[i]);
}
for (int i=0;i<matriz.length;i++)
{
for(int j=0;j<matriz.length;j++)
{
matriz[i][j]=new JTextField();
matriz[i][j].setBounds((j+2)*25,(i+2)*25,25,25);
mayor.add(matriz[i][j]);
matriz[i][j].addActionListener( this );
}
}
int p=matriz[a-1][a-1].getX();
int w=matriz[a-1][a-1].getY();
aceptar=new JButton("Aceptar");
aceptar.setBounds ( p+80, 40, 100, 30 );
aceptar.addActionListener( this );
mensaje=new JTextArea();
scrollpane=new JScrollPane(mensaje);
scrollpane.setBounds(p+80,80,300,300);
String cadena=new String("");
for(int c=0;c<(p/2.9);c++)
{
cadena+=" ";
}
mayor.setText(cadena);
String cadena1=new String("");
for(int d=0;d<(w/14);d++)
{
cadena1+="\n";
}
mayor.setText(cadena+cadena1);
mensaje.setEditable(false);
mayor.add(aceptar);
mayor.add(scrollpane);
mayor.setEditable(false);
contenedor.add(scrollpanemayor);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setTitle("INGRESO DE MATRIZ DE ADYACENCIA");
setSize(607,507);
setLocationRelativeTo(null);
show ();
matriz[0][0].grabFocus();
}
public int ingreso(String men)
{
boolean ban=true;
int a=0;
int contador=0;
do
{
try
{
a=Integer.parseInt(JOptionPane.showInputDialog(null,men,"Entrada de datos",JOptionPane.QUESTION_MESSAGE));
ban=true;
if(a<=1||a>148)
throw new Exception("Tamaño inválido");
}
catch(NumberFormatException e)
{
contador++;
JOptionPane.showMessageDialog(null,"Solo ingrese números enteros","Error",JOptionPane.ERROR_MESSAGE);
ban=false;
}
catch(Exception e)
{
contador++;
JOptionPane.showMessageDialog(null,e.getMessage(),"Error",JOptionPane.ERROR_MESSAGE);
ban=false;
}
if(contador==3)
System.exit(0);
}
while(ban==false);
return a;
}
public void actionPerformed(ActionEvent evento)
{
if(evento.getSource()==aceptar)
{
long adyacencia[][]=new long[a][a];
try
{
for (int i=0;i<a;i++)
for(int j=0;j<a;j++)
{
if((matriz[i][j].getText()).equals(""))
throw new Exception("Faltaron valores por ingresar");
else
if(matriz[i][j].getText().contains("-"))
{
throw new Exception("Los enlaces no pueden tener distancias negativas\n");
}
else
if(matriz[i][j].getText().equals("i"))
adyacencia[i][j]=999999999;
else
{
if(((matriz[j][j].getText()).contains("i")))
throw new Exception(" Los bucles no pueden ser infinitos\n");
else
if((matriz[i][j].getText()).contains("1")||(matriz[i][j].getText()).contains("2")||(matriz[i][j].getText()).contains("3")||(matriz[i][j].getText()).contains("4")||(matriz[i][j].getText()).contains("5")||(matriz[i][j].getText()).contains("6")||(matriz[i][j].getText()).contains("7")||(matriz[i][j].getText()).contains("8")||(matriz[i][j].getText()).contains("9")||(matriz[i][j].getText()).contains("i"))
adyacencia[i][j]=Long.parseLong(matriz[i][j].getText());
else
if(i==j&&((matriz[i][j].getText()).contains("0")))
adyacencia[i][j]=Long.parseLong(matriz[i][j].getText());
else
throw new Exception("Si va a ingresar letras, ingrese sólo la i\nLa i representa Infinito\nCeros solo en la diagonal principal");
}
}
}
catch(Exception e)
{
for (int k=0;k<a;k++)
for(int l=0;l<a;l++)
adyacencia[k][l]=0;
JOptionPane.showMessageDialog(null,e.getMessage(),"Error",JOptionPane.ERROR_MESSAGE);
matriz[0][0].grabFocus();
}
Logica x=new Logica();
Long t,t2;
t=System.nanoTime();
String resultado=x.floyd(adyacencia);
t2=System.nanoTime();
resultado+="\nEl tiempo de ejecución es:\n"+(t2-t)+" nanosegundos";
mensaje.setText(resultado);
}
}
}
Forma de compilar y ejecutar
editarPara 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 Windows 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 Java 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
editarEl 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
editarEsta es la matriz de adyacencia de un grafo que puede ser utilizada para probar la efectividad del algoritmo: La i representa infinito.
| 1 | 2 | 3 | 4 | |
| 1 | 0 | 5 | i | i |
| 2 | 50 | 0 | 15 | 5 |
| 3 | 30 | i | 0 | 15 |
| 4 | 15 | i | 5 | 0 |
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
editar- 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 mejor la solución, es decir, la óptima, es mucho mejor usar el enfoque dinámico, ya que éste no repite operaciones y acelera un poco el proceso de solución.
- Cuando se implementa el algoritmo tiene una pequeña desventaja, y es que, debido a su enfoque dinámico, realiza un uso masivo de memoria, lo cual puede no ser muy conveniente si se están usando otras aplicaciones que requieran usar buena parte de la memoria.