Performance de l'algorithme de chemin le plus court dans l'API JUNG

Question

I utiliser l'API JUNG pour calculer des chemins les plus courts entre plusieurs noeuds de graphes moyen grand (20 à 100 noeuds). En ce moment je suis sur mes itérer nœuds et utiliser la simple fonction de « ShortetsPath » pour calculer le chemin le plus court pour deux noeuds. Tous les chemins les plus courts sont mis dans 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);
}

}

Je voudrais accélérer le calcul parce que je dois calculer cela pour de nombreux graphiques et de noeuds. Pour autant que je sache, ne Dijkstra est disponible dans l'API JUNG. Mes questions sont les suivantes: Puis-je utiliser Dijkstra pour dynamiser la performance? D'autres algorithmes disponibles dans l'API JUNG? Ne serait-il judicieux d'utiliser une autre implémentation graphique qui offre des méthodes plus différentes pour les chemins les plus courts?

Merci à ce jour:)

Answer 1

La classe UnweightedShortestPath en JUNG utilise une largeur d'abord, l'algorithme de recherche, qui a l'exécution O (n ^ 2). L'algorithme de Dijkstra travaille essentiellement le même, juste pour des graphes pondérés au lieu de graphes non pondérés, donc l'exécution de c'est aussi O (n ^ 2).

Cependant, il semble que vous êtes intéressé par les distances entre toutes les paires possibles de noeuds dans votre graphique, mais vous utilisez une approche par paires. Ainsi, votre durée totale d'exécution est O (n * n ^ 2) = O (n ^ 3). Au lieu de cela, vous pouvez utiliser un algorithme de chemin le plus court global comme l'algorithme de Johnson ( http://en.wikipedia.org/ wiki / Johnson 's_algorithm). C'est temps d'exécution O (n ^ 2 log * (n + ne)). Donc, un peu plus vite ensemble.

Il est pas mis en œuvre JUNG pour autant que je sache, mais vous pourriez être en mesure de saisir de recherche de code Google.