Complejidad del algoritmo del camino más corto por fuerza bruta

Para probar la eficiencia del algoritmo de búsqueda de la ruta más corta entre dos puntos por fuerza bruta se requieren en primer lugar dos modificaciones a la clase Grafo: la creación de dos atributos (public String rutaMasCorta e int longituRutaMasCorta) donde se almacenarán respectivamente, la ruta más corta de recorrido del grafo en forma de cadena de caracteres y la longitud de dicha ruta; y en segundo lugar, se modifica el método recorrerRutas para que haga la comparación de cada ruta recorrida y guarde la ruta más corta y la distancia de dicha ruta en las variables mencionadas anteriormente, y adicionalmente para que no muestre cada ruta evaluada. El método queda así:

// 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!).