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

}

나는이 많은 그래프와 노드 계산해야하기 때문에 내가 계산을 빠르게하고 싶습니다. 내가 아는 한, Dijkstra 만 정 API에서 사용할 수 있습니다. 그래서 제 질문은 : 다이크 스트라를 사용하여 성능을 향상시킬 수 있습니까? JUNG API에서 다른 알고리즘을 사용할 수 있습니까? 최단 경로에 대해 다른 방법을 제공하는 다른 그래프 구현을 사용하는 것이 합리적일까요?

감사 원경 :)

가

Answer 1

JUNG에서 UnweightedShortestPath 클래스 (N^2) 런타임 O를 갖는 너비 우선-검색 알고리즘을 사용한다. Dijkstra 알고리즘은 근본적으로 똑같이 작동합니다. 가중치가 적용되지 않은 그래프 대신 가중치 그래프에만 적용되므로 런타임도 O (n^2)입니다.

그러나 그래프에서 노드의 가능한 모든 쌍 사이의 거리에 관심이있는 것처럼 보이지만 쌍으로 접근합니다. 따라서 총 런타임은 O (n * n^2) = O (n^3)입니다. 대신 Johnson의 알고리즘 (http://en.wikipedia.org/wiki/Johnson 's_algorithm)과 같은 전역 최단 경로 알고리즘을 사용할 수 있습니다. 런타임 O (n^2 * log (n + ne))입니다. 전체적으로 조금 빨라졌습니다.

내가 아는 한 정에서 구현되지 않았지만 Google 코드 검색에서이 코드를 가져올 수 있습니다.