// recorre recursivamente las rutas entre un nodo inicial y un nodo final
// almacenando en una cola cada nodo visitado
private void recorrerRutas(int nodoI, int nodoF, Stack<Integer> resultado) {
// si el nodo inicial es igual al final se evalúa la ruta en revisión
if(nodoI==nodoF) {
int respuesta = evaluar(resultado);
if(respuesta < longitudMasCorta) {
longitudMasCorta = respuesta;
rutaMasCorta = "";
for(int x: resultado) rutaMasCorta+=(nodos[x]+" ");
}
return;
}
// Si el nodoInicial no es igual al final se crea una lista con todos los nodos
// adyacentes al nodo inicial que no estén en la ruta en evaluación
List<Integer> lista = new Vector<Integer>();
for(int i=0; i<grafo.length;i++) {
if(grafo[nodoI][i]!=0 && !resultado.contains(i))lista.add(i);
}
// se recorren todas las rutas formadas con los nodos adyacentes al inicial
for(int nodo: lista) {
resultado.push(nodo);
recorrerRutas(nodo, nodoF, resultado);
resultado.pop();
}
}
Una vez realizadas estas modificaciones, se crea una nueva clase de pruebas, TestGrafo, en la cual se van a crear grafos de tamaño 1 en adelante, aprovechando las letras del alfabeto romano, desde el nodo 'a' hasta el nodo 'z' en forma secuencial, se crearán las rutas para estos grafos y se realizará la búsqueda de la ruta más corta entre dos nodos aleatorios. A continuación se presenta el código completo en java de la clase TestGrafo:
import java.util.*;
public class TestGrafo {
public static void main(String[] args) {
// variables para cálculo del tiempo
long tiempo1;
long tiempo2;
double tiempo;
String cadena=""; // cadena con los posibles nodos
Random rnd = new Random(); // generador de números aleatorios
final int MAX_DIST = 50; // máxima distancia entre 2 nodos
for(char letra='a'; letra<='z'; letra++) {
cadena+=letra;
// Crea un nuevo grafo con tantos nodos como letras en la cadena
Grafo g = new Grafo(cadena);
// Crea rutas de tamaño aleatorio entre todos los nodos
for(char i='a';i<=letra;i++) {
for(char j=(char)(i+1);j<=letra; j++) {
g.agregarRuta(i, j, rnd.nextInt(MAX_DIST));
}
}
// Selecciona dos nodos aleatorios para buscar la ruta mas corta
char origen = cadena.charAt(rnd.nextInt(cadena.length()));
char destino = cadena.charAt(rnd.nextInt(cadena.length()));
// Tiempo del sistema antes del proceso
tiempo1 = System.currentTimeMillis();
// Busqueda de la ruta más corta entre los dos nodos aleatorios
g.encontrarRutaMinimaFuerzaBruta(origen, destino);
// Tiempo del sistema al finalizar el proceso
tiempo2 = System.currentTimeMillis();
// Tiempo del proceso
tiempo = (tiempo2-tiempo1)/1000.0;
// Mostrar cantidad de nodos del grafo y tiempo transcurrido
System.out.printf("%3d %,10.2f %n", cadena.length(), tiempo);
}
}
}
La ejecución del anterior programa trae los siguientes resultados para cantidad de nodos desde 1 hasta 13, con tiempos en segundos:
1 0,01 2 0,00 3 0,00 4 0,00 5 0,00 6 0,00 7 0,02 8 0,00 9 0,13 10 1,18 11 9,92 12 44,91 13 564,72
Siguiendo esta secuencia, se podría pensar que el tiempo de respuesta para 14 nodos podría estar en el orden de varias horas; puede notarse entonces que a partir de un número relativamente pequeño de nodos el tiempo para encontrar la solución se torna inmanejable. La razón de esto estriba en que la cantidad de rutas posibles que conectan los puntos de un grafo es proporcional al factorial del número de nodos en el grafo, por lo que el tiempo de ejecución de cualquier algoritmo que deba recorrer todos los nodos de un grafo será entonces del orden de O(N!).
