JUNG API中最短路徑算法的性能

Question

我使用JUNG API計算中型大圖（20到100個節點）中幾個節點之間的最短路徑。現在我正在迭代我的節點，並使用簡單的'ShortetsPath'函數來計算兩個節點的最短路徑。所有的最短路徑都放在一個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); 
} 

}

我想加速計算，因爲我要計算這個對於很多圖形和節點。據我所知，在JUNG API中只有Dijkstra可用。所以我的問題是：我可以使用Dijkstra來提升性能嗎？ JUNG API中有其他算法嗎？使用另一個爲最短路徑提供更多不同方法的圖形實現是否有意義？

感謝迄今:)

Answer 1

在JUNG的UnweightedShortestPath類使用廣度優先搜索算法，它具有爲O（n^2）運行。 Dijkstra算法的工作原理基本相同，只是加權圖而不是未加權圖，所以它的運行時間也是O（n^2）。

但是，它看起來像您對圖中所有可能的節點對之間的距離感興趣，但您使用的是成對的方法。所以你的總運行時間是O（n * n^2）= O（n^3）。相反，你可以使用像約翰遜算法這樣的全局最短路徑算法（http://en.wikipedia.org/wiki/Johnson's_algorithm）。這是運行時O（n^2 * log（n + ne））。所以整體上要快一點。

據我所知，它沒有在JUNG實現，但你可能能夠抓住它關閉谷歌代碼搜索。