Leistung kürzesten Weg Algorithmus in JUNG API

Question

Ich verwende den JUNG API kürzesten Wege zwischen mehreren Knoten in einem Medium großen Graphen zu berechnen (20 bis 100 Knoten). Im Moment bin ich Iterieren über meine Knoten und verwenden Sie die einfachen ‚ShortetsPath‘ Funktion den kürzesten Weg für zwei Knoten zu berechnen. Alle die kürzesten Wege sind in einem Arraylist setzen.

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);
}

}

Ich möchte die Berechnung beschleunigen, weil ich dies für viele Grafiken und Knoten zu berechnen haben. Soweit ich weiß, ist nur Dijkstra in dem JUNG-API zur Verfügung. Also meine Fragen sind: Kann ich Dijkstra Leistung zu steigern? Sind andere Algorithmen in dem JUNG-API zur Verfügung? welche Angebote mehr verschiedene Methoden für die kürzesten Wege würde es Sinn machen, eine andere grafische Darstellung Implementierung zu verwenden?

Dank so weit:)

Answer 1

Die UnweightedShortestPath Klasse in JUNG verwendet ein Breite-First-Search-Algorithmus, die O hat (n ^ 2) Laufzeit. Der Dijkstra-Algorithmus arbeitet im Wesentlichen die gleichen, nur für gewichtete Graphen statt ungewichteten Graphen, so Laufzeit es ist auch O (n ^ 2).

Allerdings sieht es aus wie Sie in den Abständen zwischen allen möglichen Paaren von Knoten in Ihrem Diagramm interessiert sind, aber Sie sind mit einem paarweise Ansatz. So Ihre Gesamtlaufzeit ist O (n * n ^ 2) = O (n ^ 3). Stattdessen könnte man einen globalen kürzesten Weg Algorithmus wie der Algorithmus Johnson verwenden ( http://en.wikipedia.org/ wiki / Johnson 's_algorithm). Das Laufzeit-O (n ^ 2 * log (n + ne)). So ein bisschen schneller insgesamt.

Es ist ja nicht so weit in JUNG umgesetzt, wie ich weiß, aber man könnte es packen kann, off Suche Google Code.