Prestazioni di più breve algoritmo di percorso nel JUNG API

Question

utilizza l'API JUNG calcolare percorsi più brevi tra i diversi nodi in grandi grafici medie (da 20 a 100 nodi). In questo momento sono l'iterazione sui miei nodi e utilizzare la funzione semplice 'ShortetsPath' per calcolare il percorso più breve per due nodi. Tutti i percorsi più brevi sono messi in 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);
}

}

Vorrei velocizzare il calcolo perché devo calcolare questo per molti grafici e nodi. Per quanto ne so, solo Dijkstra è disponibile nelle API JUNG. Quindi le mie domande sono: Posso usare Dijkstra per migliorare le prestazioni? Sono altri algoritmi disponibili in API JUNG? Avrebbe senso per utilizzare un'altra implementazione grafico che offre metodi più diversi per percorsi più brevi?

Grazie finora:)

Answer 1

La classe UnweightedShortestPath in JUNG utilizza un breadth-first Search-algoritmo, che ha O (n ^ 2) tempo di esecuzione. L'algoritmo di Dijkstra funziona essenzialmente la stessa, solo per grafi pesati invece di grafici non pesati, quindi di esecuzione è O (n ^ 2).

Tuttavia, sembra che ti interessa le distanze tra tutte le possibili coppie di nodi nel grafico, ma si sta utilizzando un approccio a coppie. Così il vostro tempo di esecuzione totale è O (n * n ^ 2) = O (n ^ 3). Invece si potrebbe usare un algoritmo di percorso più breve globale come l'algoritmo di Johnson ( http://en.wikipedia.org/ wiki / Johnson 's_algorithm). Questo è il tempo di esecuzione O (n ^ 2 * log (n + NE)). Quindi un po 'più veloce nel complesso.

Non è implementato in JUNG per quanto ne so, ma si potrebbe essere in grado di afferrare fuori di ricerca Google Code.