Rendimiento del algoritmo del camino más corto de la API de JUNG

Question

I utilizar la API JUNG para calcular caminos más cortos entre varios nodos en gráficos medio grandes (de 20 a 100 nodos). En este momento estoy interactuando sobre mis nodos y utilizar la función simple 'ShortetsPath' para calcular la ruta más corta para los dos nodos. Todos los caminos más cortos se ponen en un ArrayList.

UnweightedShortestPath<Vertex, SEdge> dist = new UnweightedShortestPath<Vertex, SEdge>(undir);
ArrayList<Vertex> tv = new ArrayList<Vertex>(); // contains nodes for shortestpath
ArrayList<Integer> distances = new ArrayList<Integer>(); // for the distances

for (int j = 0; j <tv.size()-1;j++){ //iterate over nodes
Vertex one = tv.get(j);

for (int k = j+1; k<tv.size();k++){ //iterate over next nodes
    Vertex two = tv.get(k);
    Number n = dist.getDistance(one, two);
    int d;
    if (n == null) {
        d = 5000000;
    }
    else {
        d = n.intValue();
    }
    distances.add(d);
}

}

Me gustaría acelerar el cálculo, porque tengo que calcular esto por muchos gráficos y nodos. Por lo que yo sé, sólo se Dijkstra está disponible en la API de JUNG. Así que mis preguntas son: ¿Puedo usar Dijkstra para mejorar el rendimiento? Son otros algoritmos disponibles en la API de JUNG? ¿Tendría sentido utilizar otra aplicación gráfica que ofrece más diferentes métodos para caminos más cortos?

Gracias hasta ahora:)

Answer 1

La clase UnweightedShortestPath en JUNG utiliza un primero en amplitud-algoritmo de búsqueda, que tiene O (n ^ 2) tiempo de ejecución. El algoritmo de Dijkstra funciona esencialmente la misma, sólo para grafos ponderados en lugar de gráficos no ponderados, así que es tiempo de ejecución es también O (n ^ 2).

Sin embargo, parece que usted está interesado en las distancias entre todos los posibles pares de nodos en el gráfico, pero que está utilizando un enfoque de dos a dos. Por lo que su tiempo de ejecución total es O (n * n ^ 2) = O (n ^ 3). En su lugar se puede utilizar un algoritmo de ruta más corta mundial como el algoritmo de Johnson ( http://en.wikipedia.org/ wiki / Johnson 's_algorithm). Eso es el tiempo de ejecución O (n ^ 2 * log (n + ne)). Así que un poco más rápido en general.

No es implementado en JUNG por lo que yo sé, pero usted podría ser capaz de agarrarlo fuera de búsqueda de Google Code.