JUNG : Custom DijkstraShortestPath

Question

이번 주에이 라이브러리를 발견했으며 첫 번째 프로젝트가 작동하여 간단한 비행 예약을 모델로 만듭니다. 내가 정점과 같은 비행 클래스 을 만든 가장자리

나는 공항 클래스

나는 각 비행 시간을 넣어 dijsktra 알고리즘 (DijkstraShortestPath)

class Airport { 
    String name; 
} 

class Flight { 
    String flight;   
    int duration; 
} 

g = new DirectedSparseMultigraph<Airport, Flight>(); 
Flight AXXX = new Flight("A57",3); 
Flight AYYY = new Flight("A53",1); 

ORY = new Airport("ORY"); 
LYS = new Airport("LYS"); 

g.addEdge(AXXX, ORY, LYS); 
g.addEdge(AYYY, LYS, ORY); 

Transformer<Flight, Integer> wtTransformer = new Transformer<Flight, Integer>() { 
     @Override 
     public Integer transform(Flight link) { 
       return link.duration;     
     }    
    }; 

DijkstraShortestPath<Airport, Flight> alg = new DijkstraShortestPath(g, wtTransformer);   
Number dist = alg.getDistance(ORY, LYS); 

이 간단한 사건을 연관 성공

을 만들었습니다 잘 작동하지만 이제는 지속 시간을 다음과 같이 계산합니다. Flight1 시작 12/01/13 12:00 및 도착 13/01/13 at 14h Flight2 시작 13/01/13 18:00 및 도착 13/01/13 at 20h

이 경우 비행 기간과 비행 시간을 계산하고 싶습니다. 우리가 비행 시간과 비행 시간뿐만 아니라 비행 시간 사이를 기다릴 필요가있는 하나에서 다른 비행까지 최단 경로를 얻으려고합니다. 그러나 DiskstraShortestPath는 Transformer 만 다음과 같이 허용합니다. 전 비행 시간을 계산하기 위해 이전 비행에 대한 참조를 얻을 수 없습니다 (대기 + 비행).

제 질문은 : 제 경우에 가장 좋은 방법은 무엇입니까?) 당신은 사람을 대답 는 (... DirectedSparseMultigraph를 상속) (... DijsktraShortestPath을 상속) 새로운 GraphType 만들기

감사를 새로운 알고리즘을 만들어보세요!

Answer 1

총 소요 시간을 최소화하려는 경우 실제로는 최단 경로 문제가 아니라 다른 종류의 개별 최적화 문제입니다. JUNG는 이산 최적화 문제에 대한 일반적인 해결책을 제공하지 않습니다.

비행 시간 (즉, 대기 시간)을 최소화하려는 경우에도 각 단계에서 그래프 (더 정확하게는 나가는 가장자리)를 필터링 할 수 있어야합니다. 이전 비행이 도착한 후 출발하는 항공기가 관련성이 있습니다. 즉, 로컬 토폴로지는 시간의 함수입니다.