Grafos: Algoritmos de Floyd y Warshall

Muchos problemas de la vida cotidiana se pueden expresar e incluso resolver en forma de grafo. Existen algoritmos que encuentran distintos tipos de soluciones, tanto booleanas como de eficiencia. El grafo se representa en una tabla (matriz, arreglo ; para los lenguajes de programacion) que se conoce como “matriz de adyacencia” y representa si existe una union entre dos nodos (boolean), o el “peso” entre dos nodos (grafo ponderado).

El algoritmo de Warshall es un ejemplo de algoritmo booleano. A partir de una tabla inicial compuesta de 0`s (no hay correspondencia inicial en el grafo) y 1`s (hay una correspondencia, llamase “flecha”, entre nodos), obtiene una nueva matriz denominada “Matriz de Clausura Transitiva” en la que se muestran todas las posibles uniones entre nodos, directa o indirectamente. Es decir, si de “A” a “B” no hay una “flecha”, es posible que si haya de “A” a “C” y luego de “C” a “B”. Luego, este resultado se vera volcado en la matriz final.

El algoritmo de Floyd es muy similar, pero trabaja con grafos ponderados. Es decir, el valor de la “flecha” que representamos en la matriz puede ser cualquier entero que se nos ocurra, o infinito. Infinito marca que no existe union entre los nodos. Esta vez, el resultado sera una matriz donde estaran representadas las distancias minimas entre nodos, seleccionando los caminos mas convenientes segun su ponderacion (“peso”). Por ejemplo, si de “A” a “B” hay 36 (km), pero de “A” a “C” hay 2(km) y de “C” a “B” hay 10 (km), el algoritmo nos devolvera finalmente que de “A” a “C” hay 12 (km).

Las implementaciones en Java son las siguientes:

ALGORITMO DE WARSHALL

import java.io.*;
public class Warshall
{
//declaracion de la tabla
static int [ ][ ]warshall;
static int n=0;

static BufferedReader leer=new BufferedReader(new InputStreamReader(System.in));

public static void main()
{
System.out.print(“Ingrese n (tamaño de la matriz n X n) : “);
try {
n=Integer.parseInt(leer.readLine());
}
catch (Exception e){}
int dato=0;
warshall=new int[n][n];
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
{
System.out.println(“Inserte la componente W(” + i + “)(” + j +”)”);
try {
dato=Integer.parseInt(leer.readLine());}
catch (Exception e){}
warshall[i][j]=dato;
}

//

for (int k=0;k<=n-1;k++)
{
for (int i=0;i<=n-1;i++)
for (int j=0;j<=n-1;j++)
warshall[i][j]=funcionwar(i,j,k);

}
System.out.println();System.out.println();
System.out.println(“Matriz de adyacencia correspondiente: “);
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
System.out.print(warshall[i][j]);
System.out.println();
}
}
public static int funcionwar(int i, int j, int k)
{
if ((warshall[i][j]==1)||((warshall[i][k]==1)&&(warshall[k][j]==1)))
return 1;
else
return 0;
}}

ALGORITMO DE FLOYD

import java.io.*;

public class Floyd

{

static int [ ][ ]floyd;

static BufferedReader leer=new BufferedReader(new InputStreamReader(System.in));
public static void main()

{

int n=0;

try {

System.out.print(“Ingrese n (tamaño de la matriz n X n) : “);

n=Integer.parseInt(leer.readLine());

floyd=new int[n][n];

for (int i=0;i<n;i++)

for (int j=0;j<n;j++)

{

System.out.println(“Inserte la componente W(” + i + “)(” + j +”)”);

floyd[i][j]=Integer.parseInt(leer.readLine());

}

}

catch(Exception e){}

for (int k=0;k<=n-1;k++)

{

for (int i=0;i<=n-1;i++)

{for (int j=0;j<=n-1;j++)

if ((floyd[i][k]!=-1)&&(floyd[k][j]!=-1))

floyd[i][j]=funcionfloyd(floyd[i][j],floyd[i][k]+floyd[k][j]);}

}

System.out.println(“Matriz de adyacencia correspondiente: “);

for (int i=0;i<n;i++)

{

for (int j=0;j<n;j++)

System.out.print(” – “+floyd[i][j]);

System.out.println();

}

}

public static int funcionfloyd(int A, int B)

{

if ((A==-1)&&(B==-1))

return -1;

else if (A==-1)

return B;

else if (B==-1)

return A;

else if (A>B)

return B;

else return A;

}      }
Nota= En el de floyd, el resultado -1 en la matriz representa distancia NO FINITA. Es decir, no se puede llegar a ese destino desde el origen.

~ por nolehagascasoaesostiposelementales en Septiembre 25, 2008.